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 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 To: agti-Mittagsseminar@lists.fu-berlin.de Message-ID: 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" 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 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 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 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 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) ================================================================== 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 ==================================================================