Subject: Mittagsseminar am 20.12.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

    Donnerstag, 20.12.2018, 12:00 Uhr, SR 055
    Kenny Chiu
    zum Thema: Distance lower bound for CDR using discrepancy theory

==================================================================

Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner
 Masterarbeit

On Thursday.


-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Verteidigung meiner Masterarbeit
Date: Mon, 10 Dec 2018 13:59:04 +0100
From: Kristin Knorr <kristin.knorr@fu-berlin.de>
To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,=20
i-studi@inf.fu-berlin.de
CC: diana.schueler@fu-berlin.de, serarenee.zentiks@fu-berlin.de

Sehr geehrte Damen und Herren,

hiermit lade ich Sie zur Verteidigung meiner Masterarbeit mit dem Titel=20
"Dynamic Connectivity for Intersection Graphs of Unit Squares=E2=80=9D ei=
n.

Die Verteidigung findet am 13.12.2018 um 12 Uhr s.t. in Raum 055 in der=20
Takustr. 9 statt.

Erstgutachter ist Prof. Dr. Wolfgang Mulzer.
Zweitgutachter ist Prof. Dr. L=C3=A1szl=C3=B3 Kozma.

Der Vortrag wird auf Englisch gehalten.

Mit freundlichen Gr=C3=BC=C3=9Fen
Kristin Knorr

Abstract:

Maintaining the connectivity of a dynamic graph is a basic problem in=20
data structure design.
A dynamic graph is continuously subjected to changes such as single=20
insertions or deletions of edges and vertices.
As a connectivity data structure has to answer the question if two=20
vertices in a graph are connected, it is sufficient to know the=20
connected components.
These can dramatically change with the deletion of one point which is=20
incident to many (otherwise) disjoint subgraphs.
Thus, the efficient handling of the connected components is crucial.

The problem becomes more challenging when the dynamic graph, whose=20
connectivity should be maintained, is an intersection graph.
In intersection graphs, the vertices represent point sets and there is=20
an edge if and only if two sets intersect.
Hence, a dynamic connectivity data structure for intersection graphs=20
also has to determine which edges are affected by the insertion or=20
deletion of one vertex.

The dynamic data structure for unit disk graphs by Kaplan et al. was=20
used as a basis for this thesis.
An unit disk graph is defined by a set of unit disks represented by=20
their centers.
Their data structure achieves an amortized update time of O(log n log=20
log n) and a worst-case query time of O(log n) for connectivity queries.

In this thesis the data structure was adapted for unit squares.
This means, that the point sets for the intersection graph are unit=20
squares, represented by their centers.
The developed data structure is able to maintain connectivity for=20
axis-aligned unit squares and unit squares rotated by 45=C2=B0.
For this purpose, an adaptation of AVL trees is devised which supports a =

faster detection of edges. Hence, the connectivity data structure=20
achieves an amortized update time of O(log n) and a worst-case query=20
time of O(log n) for connectivity queries.

==================================================================

Subject: Mittagsseminar am Di 11..12.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 11.12.2018, 12:00 Uhr s.t., SR 055
        Marijn Heule (University of Texas, Austin)
        zum Thema: Solving very hard problems:
                   Cube-and-Conquer, a hybrid SAT solving method

Zusammenfassung:
Many search problems, from artificial intelligence to combinatorics, explore large search
spaces to determine the presence or absence of a certain object. These problems are hard
due to combinatorial explosion, and have traditionally been called infeasible. The
brute-force method, which at least implicitly explores all possibilities, is a general
approach to search systematically through such spaces. Brute force has long been regarded
as suitable only for simple problems. This has changed in the last two decades, due to the
progress in satisfiability (SAT) solving, which renders brute force into a powerful
approach to deal with many problems easily and automatically.

We illustrate the strength of SAT via the Boolean Pythagorean Triples problem, which has
been a long-standing open problem in Ramsey Theory. Our parallel SAT solver allowed us to
solve the problem on a cluster in about two days using 800 cores, demonstrating its linear
time speedup on many hard problems. Due to the general interest in this mathematical
problem, our result requires a formal proof. Exploiting recent progress in
unsatisfiability proof checking, we
produced and verified a clausal proof of the smallest counterexample, which is almost 200
terabytes in size. These techniques show great promise for attacking a variety of
challenging problems arising in mathematics and computer science.

==================================================================

Subject: Mittagsseminar am 6.12.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Donnerstag, 6.12.2018, 12:00 Uhr s.t., SR 055
	Nadja Scharf
        zum Thema: Mountain decompositions (part I)

==================================================================

Subject: Mittagsseminar am 29.11.2018

This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--0nFMvX5mfEL6ilGTvHv1zEKtVGWvqtmLf
Content-Type: multipart/mixed; boundary="BxDbp8iq3JQ2doEX5G1i4XIHh77C6dYvi";
 protected-headers="v1"
From: Jonas Cleve <jonas.cleve@fu-berlin.de>
To: agti-Mittagsseminar@lists.fu-berlin.de
Message-ID: <b634311d-81fb-53d7-3053-47eea59b4bd9@fu-berlin.de>
Subject: Mittagsseminar am 29.11.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Donnerstag, 29.11.2018, 12:00 Uhr s.t., SR 055
	Jonas Cleve
        zum Thema: Edge Patrolling Beacon
--=20
Jonas Cleve                                            Office: Room 122
Research Assistant                                           Takustr. 9
AG Theoretische Informatik                        14195 Berlin, Germany
Institut f=C3=BCr Informatik                         Phone: +49 30 838 64=
039
Freie Universit=C3=A4t Berlin       https://page.mi.fu-berlin.de/jonascle=
ve/

==================================================================

Subject: Mittagsseminar am 27.11.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

Dienstag, 27.11.2018, 12:00 Uhr, SR 055
Aruni Choudhary
zum Thema: Distorted Integer grids

==================================================================

Subject: Mittagsseminar am 22.11.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Donnerstag, 22.11.2018, 12:00 Uhr s.t., SR 055
	Katharina Klost
        zum Thema: Finding Triangles in Transmission Graphs

==================================================================

Subject: Mittagsseminar 13.11.+15.11.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
sprechen am

        Dienstag, 13.11.2018, 12 Uhr, SR 055
        Max Willert
        zum Thema: Rook Visibility

und

        Donnerstag, 15.11.2018, 12 Uhr, SR 055
        Frank Hoffmann
        zum Thema: Unavoidable Patterns in Words, Part II

==================================================================

Subject: Re: [Mittagsseminar TI] [ti]  Mittagsseminar am 6.11.2018

Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
> spricht am
>
>         Donnerstag, den 8.11.2018, 12:00 Uhr s.t., SR 055, Takustr.9
>         Helmut Alt
>         zum Thema: Mehr über FPH
>
> _______________________________________________

==================================================================

Subject: Mittagsseminar am 6.11.2018

Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, den 6.11.2018, 12:00 Uhr s.t., SR 055, Takustr.9
        Günter Rote
        zum Thema: Optimal fences for separating disconnected regions

==================================================================

Subject: Mittagsseminar am 01.11.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Donnerstag, 01.11.2018, 12:00 Uhr s.t., SR 055
        Alexander Kauer
        zum Thema: An ETH-Tight Exact Algorithm for Euclidean TSP

==================================================================

Subject: Mittagsseminar am 30.10.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

     Dienstag, 30.10.2018, 12 Uhr, SR 055
     Bahareh Banyassady
     zum Thema: An Improved Sublinear-Space Algorithm for the Grid Graph
Reachability Problem.

==================================================================

Subject: Mittagsseminar 25.10.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

         Donnerstag, 25.10.2018, 12 Uhr, SR 055
          Wolfgang Mulzer
          zum Thema: Overmars, van Leeuwen, and Pseudolines

==================================================================

Subject: Mittagsseminar am 23.10.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

         Dienstag, 23.10.2018, 12:00 Uhr s.t., SR 055
         Klaus Kriegel
         zum Thema: Universal point sets for planar 3-trees

==================================================================

Subject: Mittagsseminar am 16.10.2018 und 18.10.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 16.10.2018, 12:00 Uhr s.t., SR 055
        Valeria Zahoransky
        zum Thema: On the limits of computability of the
                   Ackermann function

und am

        Donnerstag, 18.10.2018, 12:00 Uhr s.t., SR 055
        Jonas Cleve
        zum Thema: An O(kn log=C2=B2n) linear decision tree for k-SUM

==================================================================

Subject: Mittagsseminar am 11.10.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

    Donnerstag, 11.10.2018, 12:00 Uhr, SR 055
    Kenny Chiu
    zum Thema: An Elementary Approach to Lower Bounds in Geometric
Discrepancy

==================================================================

Subject: Mittagsseminar am 9.10.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 9.10.2018, 12:00 Uhr s.t., SR 055
        Boris Klemz
        zum Thema: Dispersable Book Embeddings

==================================================================

Subject: Mittagsseminar 04.10.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

         Donnerstag, 4.10., 12 Uhr, SR 055
         Katharina Klost
         zum Thema: Convex Hull of Points with Convex Projection

==================================================================

Subject: Mittagsseminar 02.10.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

         Dienstag, 02.10.2018, 12 Uhr, SR 055
          Sergio Cabello
          zum Thema: Inverse Voronoi Diagrams (Probably)

==================================================================

Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner
 Bachelorarbeit

On Thursday. The talk will be in German.


-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit
Date: Tue, 25 Sep 2018 11:49:01 +0200
From: "Claas Frederic Fandr=E9" <claas@zedat.fu-berlin.de>
To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
i-studi@inf.fu-berlin.de, renee.zentiks@fu-berlin.de

Sehr geehrte Damen und Herren,


hiermit lade ich Sie zur Verteidigung meiner Bachelorarbeit mit dem Thema=

"Didaktische Aufarbeitung der Monte-Carlo-Baumsuche" ein.
Die Verteidigung findet am 27.09.2018 um 12:00st im SR055 in der T9 statt=
=2E

Die Arbeit wurde von Prof. Wolfgang Mulzer betreut.
Zweitgutachterin ist M.Sc. Katharina Klost


Mit freundlichen Gr=FC=DFen
Claas Fandr=E9



Zusammenfassung:

In den letzten Jahren ist die Monte-Carlo-Baumsuche als Algorithmus um
Spielb=E4ume zu analysieren immer popul=E4ter und erfolgreicher geworden.=
  In
dieser Arbeit wird die M=F6glichkeit analysiert diese Inhalte auch in ein=
e
Vorlesung zu integrieren. Dazu wurden eine Herangehesweise an das
Themengebiet mit aussagekr=E4figen Beispielen und auch =DCbungsaufgaben
Entwickelt. Ziel ist es, dass die Studenten dadurch einen Vergleich
zwischen dem Monte-Carlo-Algorithmus und dem herk=F6mmlichen Minimax
algortihmus zihen k=F6nnen.

==================================================================

Subject: Mittagsseminar 25.9.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 25.9.2018, 12 Uhr, SR 055
        Lena Strobl
        zum Thema: Shellability

==================================================================

Subject: Mittagsseminar am 20.09.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

Donnerstag, 20.09.2018, 12 Uhr, SR 055
Nadja Scharf
zum Thema: Dividing Muffins Among Students

==================================================================

Subject: Mittagsseminar am 06.09.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

Dienstag, 06.09.2018, 12:00 Uhr, SR 055
Max Willert
zum Thema: Maker-Breaker-Dominator-Gamer

==================================================================

Subject: Mittagsseminar am 04.09.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

Dienstag, 04.09.2018, 12:00 Uhr, SR 055
Aruni Choudhary
zum Thema: About the Consensus-Halving problem

==================================================================

Subject: Mittagsseminar 28.8.

Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin
spricht am  Dienstag, 28.8.2018
>   Helmut Alt
>   zum Thema: "Efficient" algorithms for vertex cover
>
> ***************************************************
> Ort: Takustr. 9, Raum 055
> Uhrzeit: 12 Uhr s.t. - 12:30 Uhr
> ***************************************************

==================================================================

Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner
 Masterarbeit

On Thursday. The defense will be in German.


-------- Forwarded Message --------
Subject: 	[i-prof] Einladung zur Verteidigung meiner Masterarbeit
Date: 	Sat, 25 Aug 2018 11:07:03 +0200
From: 	David Sungaila <david.sungaila@fu-berlin.de>
To: 	i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
i-studi@inf.fu-berlin.de, renee.zentiks@fu-berlin.de



Sehr geehrte Damen und Herren,
=C2=A0
hiermit lade ich Sie herzlich zur Verteidigung meiner Masterarbeit mit
dem Titel
=E2=80=9E*C=F0=9D=9B=BF: Design and Implementation of a Transcompiler for=
 Language
Integrated Finite-State Machines in C=E2=99=AF*=E2=80=9C
ein.
=C2=A0
Ort:=C2=A0 Seminarraum 055, Takustra=C3=9Fe 9
Zeit: Donnerstag, den 30.08. um 12 Uhr (st)
=C2=A0
Betreuer und Erstgutachter ist Herr Prof. Mulzer und Zweitgutachterin
ist Frau Prof. Wolter.
Die Verteidigung findet auf *deutsch* statt.
=C2=A0
Mit freundlichen Gr=C3=BC=C3=9Fen
David Sungaila
=C2=A0
_Abstract_
C=E2=99=AF is a programming language developed by Microsoft that supports=

multiple programming paradigms. Two of these paradigms are
object-oriented programming and event-driven programming which allow
developers to implement finite-state machines in their applications.
=C2=A0
However, these implementations are not supported by a built-in
programming paradigm, syntactic sugar, or the included base class
libraries. This forces developers to either create their own robust
general purpose finite-state machines or include a third-party class
library.
=C2=A0
This master=E2=80=99s thesis discuses automata-based programming as a
programming paradigm and how C=F0=9D=9B=BF, a language designed and imple=
mented in
this thesis, will extend C=E2=99=AF with this paradigm. Furthermore, othe=
r
programming languages and code generators are compared to C=F0=9D=9B=BF i=
n their
implementations of finite-state machines. Special attention is given to
the programming language P=E2=99=AF, as its specification and goals are s=
imilar
to C=F0=9D=9B=BF.
=C2=A0
To show the practicability of the C=F0=9D=9B=BF language, its compiler is=

rewritten into C=F0=9D=9B=BF itself. This recursive bootstrapping is used=
 to
discuss the advantages and experiences of having language integrated
finite-state machines, compared to other solutions.

==================================================================

Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner
 Masterarbeit

On Thursday. The defense will be in English.


-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Verteidigung meiner Masterarbeit
Date: Mon, 20 Aug 2018 13:31:47 +0200
From: Florian Hartmann <florian.hartmann@fu-berlin.de>
To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,=20
i-studi@inf.fu-berlin.de, renee.zentiks@fu-berlin.de

Sehr geehrte Damen und Herren,

hiermit lade ich Sie herzlich zur Verteidigung meiner Masterarbeit mit=20
dem Titel =E2=80=9CFederated Learning" ein.

Die Verteidigung findet im Rahmen des Mittagsseminars der Arbeitsgruppe=20
Theoretische
Informatik am Donnerstag, den 23.08. um 12:00 Uhr s.t. im SR 055 in der=20
Takustra=C3=9Fe 9 statt.
Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut, Zweitgutachter=20
ist Prof. Dr. Ra=C3=BAl Rojas.

Ein gro=C3=9Fer Teil der Arbeit wurde bei Mozilla in Mountain View,=20
Kalifornien, verfasst.
F=C3=BCr Fragen dazu stehe ich auch zur Verf=C3=BCgung.

Mit freundlichen Gr=C3=BC=C3=9Fen
Florian Hartmann

Abstract:
Over the past few years, machine learning has revolutionized fields such =

as computer vision, natural
language processing, and speech recognition. Much of this success is=20
based on collecting vast
amounts of data, often in privacy-invasive ways. Federated Learning is a =

new subfield of machine
learning that allows training models without collecting the data itself. =

Instead of sharing data,
users collaboratively train a model by only sending weight updates to a=20
server. While this better
respects privacy and is more flexible in some situations, it does come=20
at a cost. Naively
implementing the concept scales poorly when applied to models with=20
millions of parameters. To make
Federated Learning feasible, this thesis proposes changes to the=20
optimization process and explains
how dedicated compression methods can be employed. With the use of=20
Differential Privacy techniques,
it can be ensured that sending weight updates does not leak significant=20
information about
individuals. Furthermore, strategies for additionally personalizing=20
models locally are proposed. To
empirically evaluate Federated Learning, a large-scale system was=20
implemented for Mozilla Firefox.
360,000 users helped to train and evaluate a model that aims to improve=20
search results in the
Firefox URL bar.

==================================================================

Subject: Fwd: [i-prof] [i-studi] Einladung zur
 Verteidigung meiner Bachelorarbeit

On Tuesday.
The defense will be in English.


-------- Forwarded Message --------
Subject: [i-prof] [i-studi] Einladung zur Verteidigung meiner Bachelorarb=
eit
Date: Mon, 20 Aug 2018 12:14:08 +0200
From: Anton Begehr <a.begehr@fu-berlin.de>
To: i-studi@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,=20
i-profs@inf.fu-berlin.de

Sehr geehrte Damen und Herren,

hiermit lade ich Sie herzlich zur Verteidigung meiner Bachelorarbeit mit
dem Thema =E2=80=9CLexicographic Fr=C3=A9chet Matchings with Degenerate I=
nputs" ein.

Der Vortrag findet am Di. 21.08.2018 um 12 Uhr s.t. in Raum 055=20
(Takustra=C3=9Fe 9)
statt.

Erstgutachter ist Prof. Dr. G=C3=BCnter Rote, Zweitgutachter Prof. Dr. Wo=
lfgang
Mulzer.

Der Vortrag findet auf Englisch statt.

Mit freundlichen Gr=C3=BC=C3=9Fen

Anton Begehr

Zusammenfassung:

The classical Fr=C3=A9chet distance is the minimal connecting distance ne=
eded to
monotonically traverse two paths completely. Lexicographic Fr=C3=A9chet m=
atchings
utilize the steepest descent and apply the Fr=C3=A9chet distance recursiv=
ely=20
(i.e. divide
and conquer) to minimize the time spent at a distance greater than a=20
threshold.
We take a deep dive into degenerate inputs where different matchings appe=
ar
equal when viewed at a distance. The problem of choosing one of the multi=
ple
paths through critical events at the same distance is investigated.=20
Multiple critical
events are compared using derivatives and second derivatives.

==================================================================

Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner
 Bachelorarbeit

On thursday (in German)


-------- Forwarded Message --------
Subject: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit
Date: Thu, 9 Aug 2018 11:44:25 +0200
From: Maria Hartmann <lm.hartmann@gmx.de>
To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
i-studi@inf.fu-berlin.de, renee.zentiks@fu-berlin.de

Sehr geehrte Damen und Herren,

hiermit m=F6chte ich Sie herzlich zur Verteidigung meiner Bachelorarbeit
mit dem Titel "Routing in Geometric Intersection Graphs" einladen.

Die Verteidigung findet statt am Donnerstag, dem 16.08.2018 um 12:00 Uhr
(s.t.) in SR 055.

Erstgutachter ist Prof. Dr. Wolfgang Mulzer, Zweitgutachter ist Max Wille=
rt.

Mit freundlichen Gr=FC=DFen

Maria Hartmann


Abstract:

Let S be a set of points in the plane. In a square graph QG(S), each
point is the centre of a square of bounded size. The points represent
the vertices of QG(S) and two vertices share an edge, iff their squares
intersect. There is a similar definition for region graphs: each point
is the centre of the minimum enclosing circle of a region. Two points
share an edge in the region graph RG(S), iff their respective regions
intersect. We define the edge weight in both graphs to be the Euclidean
distance between the endpoints of an edge.
This thesis describes routing schemes for a special case of region
graphs and for the general case of square graphs that allow a packet to
be routed along those graphs with a routing distance that is arbitrarily
close to the optimal distance (i.e. the length of the shortest path).

==================================================================

Subject: Mittagsseminar 09.09.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

  Donnerstag, 09.08.2018
  Alexander Kauer
  zum Thema: Parametric and Kinetic Heaps

***************************************************
Ort: Takustr. 9, Raum 055
Uhrzeit: 12:00 Uhr s.t. - 12:30 Uhr
***************************************************

==================================================================

Subject: Mittagsseminar 07.08.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

         Dienstag, 07.08.2018, 12 Uhr, SR 055
          Wolfgang Mulzer
          zum Thema: New News on the Frechet Distance

==================================================================

Subject: Mittagsseminar am 02.08

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

  Donnerstag, 02.08.2018
  Bahareh Banyassady
  zum Thema: Orthogonal Range Searching and Ball-Inheritance Problem
***************************************************
Ort: Takustr. 9, Raum 055
Uhrzeit: 12:00 Uhr s.t. - 12:30 Uhr
***************************************************

==================================================================

Subject: Mittagsseminar am 02.08

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

  Dienstag, 02.08.2018
  Bahareh Banyassady
  zum Thema: Orthogonal Range Searching and Ball-Inheritance Problem
***************************************************
Ort: Takustr. 9, Raum 055
Uhrzeit: 12:00 Uhr s.t. - 12:30 Uhr
***************************************************

==================================================================

Subject: Datumskorrektur: Mittagsseminar am 31.07.2018

On 31.07.2018 10:47, Klaus Kriegel wrote:
>
> Im Rahmen des Mittagsseminars der
> Theoretischen Informatik der FU Berlin
> spricht am
>
>     Dienstag, 31.07.2018, 12:00 Uhr, SR 055
>     Klaus Kriegel
>     zum Thema: Old facts and new results about point guards

==================================================================

Subject: Mittagsseminar am 30.07.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

    Dienstag, 30.07.2018, 12:00 Uhr, SR 055
    Klaus Kriegel
    zum Thema: Old facts and new results about point guards

==================================================================

Subject: Mittagsseminar am 26.07.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

    Donnerstag, 26.07.2018, 12:00 Uhr, SR 055
    Kenny Chiu
    zum Thema: Lower bounds on the discrepancy of a sequence

==================================================================

Subject: Mittagsseminar am 24.7. / Isotonic Regression
 by Dynamic Programming

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

  Dienstag, 24.7.2018
  Günter Rote
  zum Thema: Isotonic Regression by Dynamic Programming

***************************************************
Ort: Takustr. 9, Raum 055
Uhrzeit: 12:00 Uhr s.t. - 12:30 Uhr
***************************************************

==================================================================

Subject: Mittagsseminar 17.7.+19.7.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
sprechen am

        Dienstag, 17.7.2018, 12 Uhr, SR 055
        Max Willert
        zum Thema: Guarding orthogonal terrains

und

        Donnerstag, 19.7.2018, 12 Uhr, SR 055
        Jonas Cleve
        zum Thema: Gathering by Repulsion

==================================================================

Subject: Mittagsseminar am 12.07.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

Donnerstag, 12.07.2018, 12 Uhr, SR 055
Aruni Choudhary
zum Thema: Approximating Cech Filtrations by digitization

==================================================================

Subject: Mittagsseminar 10.07.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 10.07.2018, 12 Uhr, SR 055
         Wolfgang Mulzer
         zum Thema: Approximating the Diameter of Unit Disk Graphs

==================================================================

Subject: Mittagsseminar 5.7.

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

  Dienstag, 3.7.2018
  Alexander Kauer
  zum Thema: Dynamic Rectangular Intersection with Priorities

Zusammenfassung:
We present efficient data structures to maintain dynamic set of rectangles, 
each with priority assigned to it, such that we can efficiently find the 
rectangle of maximum priority containing a query point. Our data structures 
support insertions and deletions of rectangles. In one dimension, when 
rectangles are intervals, our most efficient data structure supports 
queries and insertions in O(logn) time, deletions in O(lognloglogn) time 
and requires linear space. When intervals are guaranteed to be 
nonoverlapping (but one can be nested within the other) we obtain a simpler 
data structure that supports all operations in O(logn) time. We can 
generalize these data structures to maintain rectangles with priorities in 
higher dimension using standard techniques based on segment trees. The 
space increases by a logarithmic factor per dimension, and we get a 
logarithmic slowdown for each operation per dimension. For nonoverlapping 
rectangles, we present a better data structure where we avoid the extra 
logarithmic factor on the query time. The general rectangular intersection 
problem with priorities and its special case of nonoverlapping rectangles 
both arise in packet classification by IP routers.

***************************************************
Ort: Takustr. 9, Raum 055
Uhrzeit: 12:00 Uhr s.t. - 12:30 Uhr
***************************************************

==================================================================

Subject: Mittagsseminar am 3.7.

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

  Dienstag, 3.7.2018
  Benjamin Burton (Queensland)
  zum Thema: Knot tabulation - a software odyssey

Zusammenfassung:
The tabulation of all prime knots up to a certain number of crossings was one of the
founding problems of knot theory in the 1800s, and continues to be of interest today.
Here we take a tour through the many and varied software challenges required to tabulate
all 350 million prime knots up to 19 crossings (a task which was finished just last
month).  Sights along the way include combinatorial, algebraic and geometric computations,
along with a mix of theoretical algorithm design and practical algorithm engineering.

***************************************************
Ort: Takustr. 9, Raum 055
Uhrzeit: 12:00 Uhr s.t. - 12:30 Uhr
***************************************************

==================================================================

Subject: Mittagsseminar 28.06.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

    Donnerstag, 28.6.2018, 12 Uhr, SR 055
    Katharina Klost
    zum Thema:
	A linear time algorithm for intersecting convex polyhedra in 3D

==================================================================

Subject: Re: [Mittagsseminar TI] [ti]  Mittagsseminar 19.6. und 21.6.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

    Dienstag, 26.6.2018, 12 Uhr, SR 055
    Helmut Alt
    zum Thema:
	Rotating Polygons Inside Polygons

==================================================================

Subject: Mittagsseminar 19.6. und 21.6.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

    Dienstag, 19.6.2018, 12 Uhr, SR 055
    Nadja Scharf
    zum Thema:
	A Tight Lower Bound for an Online Hypercube Packing Problem

und am

    Donnerstag, 21.6.2018, 12 Uhr, SR 055
    Bahareh Banyassady
    zum Thema:
	Memory-Adjustable Navigation Piles with Applications to Sorting and
Convex Hulls.

==================================================================

Subject: Mittagsseminar am 14.06.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

    Donnerstag, 14.06.2018, 12:00 Uhr, SR 055
    Kenny Chiu
    zum Thema: Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points

==================================================================

Subject: Mittagsseminar am Dienstag 12.06.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

    Dienstag, 12.6.2018, 12 Uhr, SR 055
    Klaus Kriegel
    zum Thema: Sorting on dynamic data

==================================================================

Subject: Mittagsseminar am FREITAG 8.6.2018, 14:15

Im Rahmen des Seminars der
Theoretischen Informatik der FU Berlin
spricht morgen am

    FREITAG, 8.6.2018, 14:15 Uhr,
    im *Seminarraum 006*, Institut für Informatik, Takustr. 9, 14195 Berlin

    Pritam Bhattacharya, Indian Institute of Technology (IIT), Kharagpur
    zum Thema:
    Approximation and Inapproximability of Guarding Polygons

Zusammenfassung:
The art gallery problem deals with determining the minimum number of guards (or cameras)
that are sufficient to cover or see every point in the interior of an art gallery,
assuming that the guards have 360° visibility and can see an unbounded distance. An art
gallery can be viewed as a polygon P (with or without holes) having a total of n vertices,
while certain points in P can be specified as guards. Any point z in P is said to be
visible from a guard g if the line segment joining z and g does not intersect the exterior
of P. A polygon P is said to be guarded by a set of chosen guards if every interior point
of P is visible from some guard within the guard set. This problem was first posed by
Victor Klee at a conference in 1973, and in course of time it has become one of the
important problems in computational geometry with extensive applications to surveillance
of buildings like airport terminals, railway stations etc.

Most of the standard variants of the art gallery problem have been known to be NP-hard
(though not NP-complete) since a long time, and very recently, these problems were shown
to be ETR-complete. In 1998, Eidenbenz, Stamm and Widmayer established that the art
gallery problem is APX-hard. They also proved that, especially when dealing with input
polygons containing holes, the approximation ratio of O(log n) obtained by Ghosh in 1986
is in fact tight. In 2015, Bhattacharya, Ghosh and Roy showed that the approximation ratio
lower bound of Ω(log n) holds even for the subclass of polygons with holes that are weakly
visible from an edge. However, for the case of simple polygons without holes, a PTAS has
been proposed very recently by Katz for vertex guarding the subclass of simple polygons
that are weakly visible from an edge.

Ghosh also conjectured in 1986 that a constant-factor approximation algorithm exists for
the art gallery problem when only vertex or edge guards are used and the input is
restricted to only simple polygons without holes. In 2015, Bhattacharya, Ghosh and Roy
settled this conjecture for the special class of simple polygons (without holes) that are
weakly visible from an edge by presenting a 6-approximation algorithm for this problem.
Recently, Bhattacharya, Ghosh and Pal designed constant factor approximation algorithms
for guarding general simple polygons (without holes) using vertex guards. In this talk, we
present the outline of these approximation algorithms and  explain the core ideas behind
how they achieve the constant ratios. (see https://arxiv.org/abs/1712.05492)

==================================================================

Subject: Mittagsseminar am Donnerstag 7.6.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

    Donnerstag, 7.6.2018, 12 Uhr, SR 055
    Günter Rote
    zum Thema: Blockchain technology and the crypto-currency Bitcoin
    (preview of the Long-Night-of-Sciences, with slides in German)
<http://www.ewi-psy.fu-berlin.de/einrichtungen/weitere/institut-futur/salon-futur/180528_SalonFutur_15.html>

==================================================================

Subject: Re: [Mittagsseminar TI] Mittagsseminar am 05.06.2018

Im Betreff steht das korrekte Datum, der Vortrag ist nat=C3=BCrlich am

    Dienstag, 05.06.2018, 12 Uhr, SR 055

Jonas Cleve - 2018-06-04, 16:42:
> Im Rahmen des Mittagsseminars der
> Theoretischen Informatik der FU Berlin
> spricht am
>=20
>     Donnerstag, 15.02.2018, 12 Uhr, SR 055
>     Jonas Cleve
>     zum Thema: Approximate Convex Hull of Data Streams
>=20
>=20
>=20
> _______________________________________________
> agti-Mittagsseminar mailing list
> agti-Mittagsseminar@lists.fu-berlin.de
> https://lists.fu-berlin.de/listinfo/agti-mittagsseminar
>=20
>=20
>=20

==================================================================

Subject: Mittagsseminar am 05.06.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

    Donnerstag, 15.02.2018, 12 Uhr, SR 055
    Jonas Cleve
    zum Thema: Approximate Convex Hull of Data Streams

==================================================================

Subject: Mittagsseminar 31.5.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Donnerstag, 31.5.2018, 12 Uhr, SR 055
        Max Willert
        zum Thema: Delaunay Triangulation of Points on Circles

==================================================================

Subject: Mittagsseminar 29.05.2018

Hello everyone,

during the Mittagsseminar on 29.05.2018 I will present the eertree and some 
applications and extensions of it.

An eertree is a relatively simple tree-like data structure with a nice 
construction. It allows solving several problems regarding palindromes in 
strings with a good runtime and little space (i.e. mostly linear in the input).

The eertree was introduced by Mikhail Rubinchik and Arseny M. Shur in 2015. 
You can find a pre-print under arXiv:1506.04862 .

Sorry for the late email, I just learned about this mailing list.

Have a nice evening,
Alexander

==================================================================

Subject: Mittagsseminar 05.04.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

       Donnerstag, 23.05.2018, 12 Uhr, SR 055
        Wolfgang Mulzer
        zum Thema: APSP in Geometric Intersection Graphs

==================================================================

Subject: Mittagsseminar am 17.5.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

    Donnerstag, 17.05.2018, 12:00 Uhr, SR 055
    Aruni Choudhary
    zum Thema: Ham-Sandwich is Equivalent to Borsuk-Ulam

==================================================================

Subject: Mittagsseminar am 15.5.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 15.5.2018, 12:00 Uhr s.t., SR 055
        Katharina Klost
        zum Thema: Very strong rainbow colorings in cactus graphs

==================================================================

Subject: Mittagsseminar am 8.5.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 8.5.2018, 12:00 Uhr s.t., SR 055
        Boris Klemz
        zum Thema: Hamiltonian Cycles in Squares of Biconnected Graphs

==================================================================

Subject: Mittagsseminar am 03.05.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
sprechen am

        Donnerstag, 03.05.2018, 12 Uhr, SR 055
        Bahareh Banyassady
        zum Thema: A New Balanced Subdivision of a Simple Polygon for
Time-Space Trade-off Algorithms

==================================================================

Subject: Mittagsseminar am 26.4.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Donnerstag, 26.4.2018, 12:00 Uhr s.t., SR 055
        Günter Rote
        zum Thema: Free collinear sets in planar graph drawings

==================================================================

Subject: Mittagsseminar 24.04.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
sprechen am

        Dienstag, 24.04.2018, 12 Uhr, SR 055
        Nadja Scharf
        zum Thema: A Lower Bound on the Area of a 3-Coulored Disk Packing=

--=20
Nadja Scharf
Freie Universit=C3=A4t Berlin
Institut f=C3=BCr Informatik
AG Theoretische Informatik
Takustra=C3=9Fe 9, Raum 122
14195 Berlin

==================================================================

Subject: Mittagsseminar 19.4. Corrigendum

 Im Rahmen des Mittagsseminars der
> Theoretischen Informatik der FU Berlin
> spricht am
>
>
>         Donnerstag, 19.4.2018, 12 Uhr, SR 055
>         Helmut Alt
>         zum Thema: PTAS' for Packing a Maximum Number of Unit Circles into a Given _*Rectangle*_ or Fat _*T*__*riangle*_

==================================================================

Subject: Re: [Mittagsseminar TI] [ti]  Mittagsseminar 19.4.

Im Rahmen des Mittagsseminars der
> Theoretischen Informatik der FU Berlin
> spricht am
>
>
>         Donnerstag, 19.4.2018, 12 Uhr, SR 055
>         Helmut Alt
>         zum Thema: PTAS' for Packing a Maximum Number of Unit Circles into a Given Square or Fat Rectangle
>

==================================================================

Subject: Mittagsseminar 10.4.+12.4.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
sprechen am

        Dienstag, 10.4.2018, 12 Uhr, SR 055
        Max Willert
        zum Thema: Something we did in Japan

und

        Donnerstag, 12.4.2018, 12 Uhr, SR 055
        Jonas Cleve
        zum Thema: Playing Tetris is hard

==================================================================

Subject: Mittagsseminar 05.04.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

       Donnerstag, 05.04.2018, 12 Uhr, SR 055
        Wolfgang Mulzer
        zum Thema: Asymmetric convex intersection testing

==================================================================

Subject: Mittagsseminar am 29.03. und 03.04.2018
 (UPDATED and EXTENDED)

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin spricht am

        Donnerstag 29.03.2018, 12:00 Uhr, SR 055
        Man Kwun Chiu
        zum Thema: High Dimensional Consistent Digital Segments
        *note change of speaker and topic*

und am

        Dienstag, 03.04.2018, 12:00 Uhr, SR 055
        G=FCnter Rote
        zum Thema: Counting plane graphs with so-called production matric=
es
        *note change of date*

==================================================================

Subject: Mittagsseminar am 27. und 29. 3. 2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlinspricht am

        Dienstag, 27.3.2018, 12:00 Uhr, SR 055
        Christian Schneider
        zum Thema:
        Untersuchung der Conway-Folge mittels endlicher Automaten nach Litherland
        (Bachelor-Vortrag, auf deutsch)

und am

        Donnerstag, 29.3.2017, 12:00 Uhr, SR 055
        Günter Rote
        zum Thema: Counting plane graphs with so-called production matrices

==================================================================

Subject: Mittagsseminar am Dienstag, 13.3. und Donnerstag,
 15.3.

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 13.03.2018, 12 Uhr, SR 055
        Frank Hoffmann
        zum Thema: Unavoidable Pattern in Words

und am
        Donnerstag, 15.03.2018, 12 Uhr, SR 055
        Bahareh Banyassady
        zum Thema: A Framework for In-Place Graph Algorithms

==================================================================

Subject: Mittagsseminar am Dienstag,
 13.3. und Donnerstag, 15.3.

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 13.03.2018, 12 Uhr, A3, SR 055
        Frank Hoffmann
        zum Thema: Unavoidable Pattern in Words

und am
        Donnerstag, 15.03.2018, 12 Uhr, SR 055
        Bahareh Banyassady
        zum Thema: A Framework for In-Place Graph Algorithms

==================================================================

Subject: Mittagsseminar 8.3.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Donnerstag, 8.3.2018, 12 Uhr, SR 055
        Nadja Scharf
        zum Thema: Approximation Schemes for Covering and Packing Problems

==================================================================

Subject: Mittagsseminar 22.2.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 22.2.2018, 12 Uhr, SR 055
        Katharina Klost
        zum Thema: Girth in disk graphs and triangles in transmission graphs

==================================================================

Subject: Mittagsseminar 22.2.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 22.2.2018, 12 Uhr, SR 055
        Katharina Klost
        zum Thema: Girth in disk graphs and triangles in transmission graphs

==================================================================

Subject: Mittagsseminar 20.2.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 20.2.2018, 12 Uhr, SR 055
        Max Willert
        zum Thema: Clique Problem in Intersection Graphs of Ellipses

==================================================================

Subject: Mittagsseminar am 15.02.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

    Donnerstag, 15.02.2018, 12 Uhr, SR 055
    Jonas Cleve
    zum Thema: Dynamic Time Warping: Breaking the Quadratic Barrier

==================================================================

Subject: Mittagsseminar 13.2.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

     Dienstag, 13. Februar  2018, 12:00 Uhr s.t., Arnimallee 3, SR 130
     Andrei Asinowski
     zum Thema: Enumeration of polyominoes with fixed perimeter defect

==================================================================

Subject: Mittagsseminar am 08.02.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Donnerstag, 08.02.2018
        Boris Klemz
        zum Thema: 1-Planar Graphs


***************************************************

Ort: Takustraße 9, Raum 055
Uhrzeit: 12:00 Uhr s.t.

***************************************************

==================================================================

Subject: Re: [Mittagsseminar TI] [ti]  Mittagsseminar am Dienstag,
 16.1. und Donnerstag, 18.1.

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

	Dienstag, 6.2.2018, 12 Uhr, A3, SR 130
	Helmut Alt
	zum Thema: Don't rock the boat: Unloading is difficult

>

==================================================================

Subject: Mittagsseminar am Donnerstag 1.2.

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

   Donnerstag, 1.2.2018
   Günter Rote
   über Max-diameter 3-clustering

***************************************************

Ort: Takustraße 9, Seminarraum 055
Uhrzeit: 12:00 Uhr s.t.

***************************************************

==================================================================

Subject: Mittagsseminar am Dienstag, 23.1. und Donnerstag,
 25.1.

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

        Dienstag, 23.01.2018, 12 Uhr, A3, SR 130
        Bahareh Banyassady
        zum Thema: Output Sensitive Algorithms for Approximate Incidences
and Their Applications

und am
        Donnerstag, 25.01.2018, 12 Uhr, SR 055
        Frank Hoffmann
        zum Thema: Vertex Guards in Simple Polygons- Constant Factor
Approximation

==================================================================

Subject: Mittagsseminar am Dienstag, 16.1. und Donnerstag,
 18.1.

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am
	
	Dienstag, 16.1.2018, 12 Uhr, A3, SR 130
	Julian Habib
	zum Thema: Robot Motion Planning Algorithmen und Visualisierung

und am
	Donnerstag, 18.1.2018, 12 Uhr, SR 055
	Claudia Dieckmann
	zum Thema: Parallel Motion Planning: Coordinating a Swarm of Labeled 
Robots with Bounded Stretch

==================================================================

Subject: Mittagsseminar 11.01.18

m Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

       Dienstag, 11.01.2018, 12 Uhr, SR 055 (Takustr. 9)
        Nadja Scharf
        zum Thema:
        A simple proof that the (n^2 - 1)-puzzle is hard

==================================================================

Subject: Mittagsseminar 09.01.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

       Dienstag, 09.01.2018, 12 Uhr, SR 130 (Arnimallee 3)
        Aruni Choudhary
        zum Thema:
        Approximation Algorithms for Vietoris-Rips and Cech Filtrations

==================================================================

Subject: Mittagsseminar 04.01.2018

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

       Donnerstag, 04.01.2018, 12 Uhr, SR 055
        Wolfgang Mulzer
        zum Thema: Max Cut in Planar Graphs

==================================================================