Subject: Mittagsseminar am 17.12.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 17.12.2015 Yannik Stein zum Thema: Approximating the Simplicial Depth *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 15. u. 17.12.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 15.12.2015 Boris Klemz zum Thema: Strongly Monotone Drawings of Planar Graphs am Donnerstag, 17.12.2015 Yannik Stein zu einem noch bekanntzugebenden Thema *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 08. u. 10.12.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 08.12.2015 Helmut Alt zum Thema: Mahaney's Theorem am Donnerstag, 10.12.2015 Klaus Kriegel zum Thema: Universal Point Sets for One-bend Drawings *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagssemianr am 01. u. 03.12.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 01.12.2015 Heuna Kim zum Thema: How to read Coxeter Diagrams am Donnerstag, 03.12.2015 Günter Rote zum Thema: The Towers of Bucharest and Loop-Free Algorithms for Gray Codes *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 24. u. 26.11.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 24.11.2015.2015 Wolfgang Mulzer zum Thema: Geodesic Spanners for Points on a Polyhedral Terrain am Donnerstag, 26.11.2015 Paul Seiferth zum Thema: Optimal Deterministic Shallow Cuttings in 2D and 3D *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 17. u. 19.11.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 17.11.2015.2015 Günter Rote zum Thema: Optimal homotopic systems of paths am Donnerstag, 19.11.2015 Bahareh Banyassady zum Thema: Finding median in read-only memory on integer input *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 10. u. 12.11.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 10.11.2015.2015 Lena Schlipf zum Thema: Finding largest rectangles in convex polygonsam am Donnerstag, 12.11.2015 Nadja Scharf zum Thema: CIRCLE PLACEMENT is NP-hard *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: am 05.11.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 05.11.2015 Romain Grunert zum Thema: On the NP-completeness of the Slither Link Puzzle *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 03. u. 05.11.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 03.11.2015 Frank Hoffmann zum Thema: 2-fold 9-coloring of planar graphs am Donnerstag, 05.11.2015 Romain Gruner zu einem noch bekanntzugebenden Thema *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 29.10.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 29.10.2015 Yannik Stein zum Thema: Points Surrounding the Origin *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 27. u. 29.10.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 27.10.2015 Boris Klemz zum Thema: Computing Minimum Tree Supports for Hypergraphs am Donnerstag, 22.10.2015 Yannik Stein zu einem noch bekanntzugebenden Thema *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 20. u. 22.10.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 20.10.2015 Klaus Kriegel zum Thema: Even triangulations of mosaics am Donnerstag, 22.10.2015 Marcel Eberhardt zum Thema: An In-Depth Analysis of Data Structures Derived from van-Emde-Boas-Trees (Mastervortrag) *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Fwd: Einladung zur Verteidigung meiner Masterarbeit -------- Forwarded Message -------- Subject: Einladung zur Verteidigung meiner Masterarbeit Date: Mon, 19 Oct 2015 13:29:29 +0200 From: Marcel Ehrhardt To: i-studi@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de, i-profs@inf.fu-berlin.de CC: renee.zentiks@fu-berlin.de Sehr geehrte Damen und Herren, hiermit lade ich Sie herzlich zur Verteidigung meiner Masterarbeit mit dem Titel =E2=80=9EAn In-Depth Analysis of Data Structures Derived from van-Emde-Boas-Trees=E2=80=9D ein. Die Verteidigung findet am Donnerstag, dem 22.10.2015, um 12:00 Uhr in Raum 055 in der Takustr. 9 statt. Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut. Zweitgutachter ist Dr. Klaus Kriegel. Zusammenfassung: IP-packet routing is one of the most practical solved problems in computer science with millions of routed packets per second. The algorithmic problem behind it is the so-called predecessor problem. Assuming a universe U, in this problem one can query a set S =E2=8A=86 U = for the *predecessor* of an element q within the set S, i.e. max{x =E2=88=88 S | = x < q}. If the set S can be manipulated, the problem is called the *dynamic* predecessor problem, otherwise it is called the *static* predecessor problem. I give an overview of several different data structures for the w-bit word RAM on *bounded integer universes*, i.e. U =3D {0, ..., 2^w =E2=88=92= 1}. Those data structures are based on the van-Emde-Boas-Tree [BKZ76]. For each data structure I work out the details of the algorithms by giving pseudo-code and for some of them I present new techniques, which give an easier and clearer presentation of the data structure and the algorithms. Last but not least, I answer an open problem concerning the space usage stated by Bose et al [Bos+13]. Mit freundlichen Gr=C3=BC=C3=9Fen Marcel Ehrhardt ----------------------- [BKZ76] P. van Emde Boas, R. Kaas, and E. Zijlstra. =E2=80=9CDesign and implement= ation of an efficient priority queue=E2=80=9D. In: Mathematical systems theory = 10.1 (1976), pp. 99=E2=80=93127. issn: 0025-5661. doi: 10.1007/BF01683268. url= : 10.1007/BF01683268. [Bos+13] Prosenjit Bose, Karim Dou=C3=AFeb, Vida Dujmovi=C4=87, John Howat, and Pa= t Morin. =E2=80=9CFast Local Searches and Updates in Bounded Universes=E2=80=9D. I= n: Comput. Geom. Theory Appl. 46.2 (Feb. 2013), pp. 181=E2=80=93189. issn: 0925-7721= =2E doi: 10 . 1016 / j . comgeo . 2012.01.002. ================================================================== Subject: Mittagsseminar am 13. u. 15.10.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 13.10.2015 Paul Seiferth zum Thema: Routing in Unit Disk Graphs am Donnerstag, 15.10.2015 Helmut Alt zum Thema: The sausage conjecture and the sausage catastrophe *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 06.10. u. 08.10.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 06.10.2015 Bahareh Banyassady zum Thema: Computing the k-visible region with few variables und am Donnerstag, 08.10.2015 Heuna Kim zum Thema: A new bound for the number of combinatorially different convex hulls in an arrangement *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 29.09. u. 01.10.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 29.09.2015 Wolfgang Mulzer zum Thema: Radial Orderings and Order Types und am Donnerstag, 01.10.2015 G=C3=BCnter Rote zum Thema: The Maximum Number of Minimal Dominating Sets in a Tree, and Algorithms for Enumerating Them *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 24.09.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnstag, 24.09.2015 Lena Schlipf zum Thema: Quickest Visibility Queries *************************************************** Ort: Takustr. 9, Raum 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 4.9.2015 (HEUTE, Raum 049) Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Freitag, 4.9.2015 Manfred Scheucher (TU Graz) zum Thema: Orthogeodesic point set embeddings of outerplanar graphs *************************************************** Ort: Takustr. 9, RM *049* (*ge=E4nderter Raum*) Uhrzeit: 12:00 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am FREITAG, 31.7.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am *Freitag*, 28.07.2015 Shay Moran, Technion (Haifa) und MPI (Saarbr=FCcken) zum Thema: Shattering, Graph Orientations, and Connectivity *************************************************** Ort: Takustr. 9, Raum 055 Uhrzeit: 12:00 Uhr s.t. - 12:45 Uhr *************************************************** ================================================================== Subject: Mittagsseminar am 28.07.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 28.07.2015 Matthias Henze zum Thema: Improving a quantitative Doignon-Bell-Scarf Theorem *************************************************** Ort: Takustr. 9, Raum 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 21. u 23.07.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 21.07.2015 Luca Keidel zum Thema: Packen von Polygonen mit Hilfe von Metaheuristiken am Donnerstag, 23.07.2015 Romain Grunert zum Thema: Schoenflies Conjecture *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 02.07.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 02.07.2015 Wolfgang Mulzer zum Thema: Pudlak's Algorithm for 3-SAT *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 11.06.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 11.06.2015 Max Willert zum Thema: Tight bounds for conflict-free chromatic guarding of orthogonal art galleries *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 02. u. 04.06.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 02.06.2015 Wolfgang Mulzer zum Thema: Another Proof of Chernoff's Bound und am Donnerstag, 04.06.2015 Heuna Kim zum Thema: The Thing I Solved in Mexico *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 28.05.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 28.05.2015 Klaus Kriegel zum Thema: Free Edge Lengths in Plane Graphs *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 26. u. 28.05.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 26.05.2015 Karl Bringmann zum Thema: Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping Abstract: Longest common subsequence and edit distance are classic similarity measures of strings. Dynamic time warping is a classic similarity measure of curves. These measures can be computed by simple quadratic time dynamic programming algorithms, and despite much effort no algorithms with significantly better running time are known. We prove that, even restricted to binary strings or one-dimensional curves, respectively, these measures do not have strongly subquadratic time algorithms, i.e., no algorithms with running time O(n^{2=E2=88=92eps= }) for any eps>0, unless the Strong Exponential Time Hypothesis fails. We generalize the result to edit distance for arbitrary fixed costs of the four operations (deletion, insertion, matching, substitution), by identifying trivial cases that can be solved in constant time, and proving quadratic-time hardness on binary strings for all other cost choices. und am Donnerstag, 28.05.2015 Klaus Kriegel zum einem noch bekannt zu gebenden Thema *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 19. u. 21.05.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 19.05.2015 Tudor Soroceanu zum Thema: Implementierung eines Approximations-Algorithmus f=C3=BCr die Berechnung der diskreten Frechet-Metrik (Bachelorvortrag) und am Donnerstag, 21.05.2015 Frank Hoffmann zum Thema: Encompassing Colored Planar Graphs *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 12.05.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 12.05.2015 Yannik Stein zum Thema: Time-Space Tradeoff for the All-Nearest-Larger-Neighbor Problem *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 07.05.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 07.05.2015 Helmut Alt zum Thema: Trench Digging, Barriers, and Opaque Set *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: am 05.05.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 05.05.2015 Romain Grunert zum Thema: Sliding Tokens on Trees *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 28. u. 30.04.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 28.04.2015 Wolfgang Mulzer zum Thema: Sample Compression II und am Donnerstag, 30.04.2015 Paul Seiferth zum Thema: Approximate k-flat Nearest Neighbor Search *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 23.04.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 23.04.2015 Matthias Henze zum Thema: What is the 84-shape? *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Grillen Hi everyone, Yannik and Mathias reminded me kindly that I might want to use the barbeque. However, Thursday is the only day I still have time before my departure. So Thursday around 7 pm some food will be provided. Be there or be square! ;) best Till ================================================================== Subject: Mittagsseminar am 14. u. 16.04.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 14.04.2015 Boris Klenmz zum Thema: Recognizing Weighted Disk Contact Graphs (Bewerbungsvortrag) und am Donnerstag, 16.04.2015 Günter Rote zum Thema: The Blaschke-Petkantschin formula for the hyperplane spanned by random points *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 07.04.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 07.04.2015 Wolfgang Mulzer zum Thema: The Sample-Compression Conjecture *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 2.4.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 05.03.2015 Helmut Alt An approximation algorithm for the optimal packing of convex polygons under translation Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. ================================================================== Subject: Reminder: Mittagsseminar today 14:00 (!) in SR 053 (!) Please not the unusual time and room. -------- Forwarded Message -------- Subject: Re: Mittagsseminar am 24.03.2015 -> 26.03.2015 Date: Mon, 23 Mar 2015 13:49:49 +0100 From: Wolfgang Mulzer To: agti-Mittagsseminar@lists.fu-berlin.de CC: Fr=C3=A9d=C3=A9ric Meunier Since the ERC-workshop is taking place simultaneously at Seminaris, tomorrow's Mittagsseminar has been rescheduled. The new date and time are= : Thursday, 26.03.2015 14:00 st Takustr. 9, SR 053 Fr=C3=A9d=C3=A9ric Meunier Hedetniemi=E2=80=99s conjecture for Kneser hypergraphs Abstract: One of the most famous conjectures in graph theory is Hedetniemi=E2=80=99s conjecture stating that the chromatic number of the categorical product of graphs is the minimum of their chromatic numbers. Using a suitable extension of the definition of the categorical product, Zhu proposed in 1992 a similar conjecture for hypergraphs. With the help of a technique originally introduced by Jiri Matousek and based on combinatorial counterparts of the Borsuk-Ulam theorem, it is possible to prove that Zhu=E2=80=99s conjecture is true for Kneser hypergraphs, which= become the first non-trivial and explicit family of hypergraphs satisfying this conjecture. A similar approach also allows to exhibit new families of graphs that satisfy Hedetniemi=E2=80=99s conjecture. This is joint work w= ith Hossein Hajiabolhassan. ================================================================== Subject: Re: [Mittagsseminar TI] Mittagsseminar am 24.03.2015 -> 26.03.2015 Since the ERC-workshop is taking place simultaneously at Seminaris, tomorrow's Mittagsseminar has been rescheduled. The new date and time are= : Thursday, 26.03.2015 14:00 st Takustr. 9, SR 053 Fr=C3=A9d=C3=A9ric Meunier Hedetniemi=E2=80=99s conjecture for Kneser hypergraphs Abstract: One of the most famous conjectures in graph theory is Hedetniemi=E2=80=99s conjecture stating that the chromatic number of the categorical product of graphs is the minimum of their chromatic numbers. Using a suitable extension of the definition of the categorical product, Zhu proposed in 1992 a similar conjecture for hypergraphs. With the help of a technique originally introduced by Jiri Matousek and based on combinatorial counterparts of the Borsuk-Ulam theorem, it is possible to prove that Zhu=E2=80=99s conjecture is true for Kneser hypergraphs, which= become the first non-trivial and explicit family of hypergraphs satisfying this conjecture. A similar approach also allows to exhibit new families of graphs that satisfy Hedetniemi=E2=80=99s conjecture. This is joint work w= ith Hossein Hajiabolhassan. On 03/20/2015 05:22 PM, Wolfgang Mulzer wrote: >=20 > Im Rahmen des Mittagsseminars der > Theoretischen Informatik der FU Berlin > spricht am >=20 > Dienstag, 24.03.2015 > Fr=C3=A9d=C3=A9ric Meunier > zum Thema: Hedetniemi=E2=80=99s conjecture for Kneser hypergrap= hs >=20 > Abstract: One of the most famous conjectures in graph theory is > Hedetniemi=E2=80=99s conjecture stating that the chromatic number of th= e > categorical product of graphs is the minimum of their chromatic numbers= =2E > Using a suitable extension of the definition of the categorical product= , > Zhu proposed in 1992 a similar conjecture for hypergraphs. With the hel= p > of a technique originally introduced by Jiri Matousek and based on > combinatorial counterparts of the Borsuk-Ulam theorem, it is possible t= o > prove that Zhu=E2=80=99s conjecture is true for Kneser hypergraphs, whi= ch become > the first non-trivial and explicit family of hypergraphs satisfying thi= s > conjecture. A similar approach also allows to exhibit new families of > graphs that satisfy Hedetniemi=E2=80=99s conjecture. This is joint work= with > Hossein Hajiabolhassan. >=20 >=20 >=20 > *************************************************** > Ort: Takustr. 9, RM 055 >=20 > Uhrzeit: 12 Uhr s.t. > *************************************************** >=20 >=20 >=20 >=20 ================================================================== Subject: Mittagsseminar am 24.03.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 24.03.2015 Fr=C3=A9d=C3=A9ric Meunier zum Thema: Hedetniemi=E2=80=99s conjecture for Kneser hypergraphs= Abstract: One of the most famous conjectures in graph theory is Hedetniemi=E2=80=99s conjecture stating that the chromatic number of the categorical product of graphs is the minimum of their chromatic numbers. Using a suitable extension of the definition of the categorical product, Zhu proposed in 1992 a similar conjecture for hypergraphs. With the help of a technique originally introduced by Jiri Matousek and based on combinatorial counterparts of the Borsuk-Ulam theorem, it is possible to prove that Zhu=E2=80=99s conjecture is true for Kneser hypergraphs, which= become the first non-trivial and explicit family of hypergraphs satisfying this conjecture. A similar approach also allows to exhibit new families of graphs that satisfy Hedetniemi=E2=80=99s conjecture. This is joint work w= ith Hossein Hajiabolhassan. *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 05.03.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 05.03.2015 Michael Gene Dobbins zum Thema: A point in a nd-polytope is the barycenter of n points in its d-faces *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 03.03.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 03.03.2015 Yannik Stein zum Thema: Centerdisks *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 26.02.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 26.02.2015 Merle Breitkreuz zum Thema: The Connectivity Game and the Hitiing Time Conjecture (Mastervortrag) *************************************************** Ort: Takustr. 9, Raum 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 24.02.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 24.02.2015 Paul Seiferth zum Thema: Fully Dynamic Reachability in Unit-Disk Graphs *************************************************** Ort: Takustr. 9, Raum 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Fwd: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit -------- Forwarded Message -------- Subject: [i-prof] Einladung zur Verteidigung meiner Bachelorarbeit Date: Tue, 10 Feb 2015 19:11:31 +0100 From: Alexander Kauer To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,=20 i-studi@inf.fu-berlin.de CC: renee.zentiks@fu-berlin.de Sehr geehrte Damen und Herren, hiermit lade ich Sie zur Verteidigung meiner Bachelorarbeit mit dem Titel= Implementation of and Experiments on Centerpoint Approximation Algorithms ein. Die Verteidigung findet Dienstag, den 17.02.2015 im Rahmen des Mittagssemiars f=FCr Theoretische Informatik um 12:00 s.t. in SR055 statt= =2E Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut, Zweitkorrektor ist Prof. Dr. Helmut Alt. Mit freundlichen Gr=FC=DFen Alexander Kauer Zusammenfassung: Der eindimensionale Median ist einer der grundlegenden Bestandteile der Informatik und Mathematik. Die Idee des Medians kann auf h=F6here Dimensionen als Centerpoint verallgemeinert werden. Hierbei zerlegen alle Hyperebenen durch einen Centerpoint die Eingabe in zwei etwa gleich gro=DFe Teile. Der bisher schnellste Algorithmus um einen Centerpoint f=FCr n Punkte in = d Dimensionen zu finden hat eine erwartete Laufzeit von O(n^(d - 1)). Durch die in d exponentielle Laufzeit ist dieser Algorithmus nur f=FCr kleinere Dimensionen sinnvoll anwendbar. Es ist kein Algorithmus bekannt um einen Centerpoint in polynomieller Laufzeit bez=FCglich sowohl n als auch beliebiger Dimension d zu finden. Aus diesem Grund sind vor allem approximative Algorithmen f=FCr dieses Themengebiet von gro=DFem Interess= e. In dieser Arbeit werden mehrere approximative Algorithmen f=FCr eine beliebige Anzahl an Dimensionen vorgestellt. Diese Algorithmen haben ein bez=FCglich Anzahl der Punkte n und der Dimension d polynomielles Laufzeitverhalten. Weiterhin wurden diese Algorithmen implementiert und deren durchschnittliche G=FCte bei zuf=E4lliger Eingabe ermittelt, da die= Algorithmen nur eine untere Schranke der G=FCte des Ergebnisses garantier= en. ================================================================== Subject: am 19.02.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 19.02.2015 Romain Grunert zum Thema: Characterising regular and critical points by local equivalence *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 10.02.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 10.02.2015 Matthias Henze zum Thema: On a reverse isodiametric inequality *************************************************** Ort: Takustr. 9, Raum 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Fwd: Einladung zur Praesentation meiner Bachelorarbeit Noon seminar Thursday. -------- Forwarded Message -------- Subject: [i-prof] Einladung zur Praesentation meiner Bachelorarbeit Date: Fri, 23 Jan 2015 22:45:06 +0100 From: Lilian Hung To: i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,=20 i-studi@inf.fu-berlin.de Sehr geehrte Damen und Herren, hiermit lade ich Sie herzlich zur Pr=C3=A4sentation meiner Bachelorarbeit= mit dem Titel Untersuchung einer Verbesserung des Algorithmus f=C3=BCr das 3SUM-Pr= oblem und Anwendung an einem 3SUM-schweren Problem ein. Die Pr=C3=A4sentation findet am Donnerstag den 05.02.2015, 12:00 Uhr st i= n SR 055, Takustra=C3=9Fe 9 statt. Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut. Zusammenfassung: Das 3SUM-Problem beschreibt das Ermitteln dreier Zahlen aus einer gegebenen Menge von n reellen Zahlen, die aufaddiert null ergeben. Bisher= hat man noch keinen vergleichsbasierten Algorithmus f=C3=BCr das 3SUM-Pro= blem gefunden, der eine schnellere Laufzeit als n=C2=B2 hat. Diese Arbeit besch=C3=A4ftigt sich mit der genaueren Analyse des Artikels =E2=80=9DThr= eesomes, Degenerates and Love-Triangles=E2=80=9D und vor allem mit dem Algorithmus= zur Erstellung eines Entscheidungsbaums mit der subquadratischen Tiefe von O(n^(3/2)*(log n)^(3/2)). Dieser wird Schritt f=C3=BCr Schritt in seinem = Aufbau und Vorgehen erl=C3=A4utert. Es wird der wichtige Unterschied zwischen Entscheidungsb=C3=A4umen und der Laufzeit von Algorithmen betrachtet. Im zweiten Teil wird das 3SUM-schwere Problem "Ein Punkt auf drei Geraden= " betrachtet. Es wird seine Komplexit=C3=A4t untersucht und gezeigt, dass d= as 3SUM-Problem transformierbar zum "Ein Punkt auf drei Geraden"-Problem ist= =2E Mit freundlichen Gr=C3=BC=C3=9Fen, Lilian Hung ================================================================== Subject: Mittagsseminar am 29.01.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 29.01.2015 Ludmila Scharf zum Thema: Continuous Dynamic Time Warping for Computing Similarity between Curves *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 27.1.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 27.1.2015 Heuna Kim zum Thema: Helly theorem for unions of convex sets *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** _______________________________________________ agti-Mittagsseminar mailing list agti-Mittagsseminar@lists.fu-berlin.de https://lists.fu-berlin.de/listinfo/agti-mittagsseminar _______________________________________________ Automatischer Mailverteiler an Gruppe 'ml-ti-mi'. Hinweise dazu siehe Hilfeseite: https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler ================================================================== Subject: Re: [Mittagsseminar TI] [ti] Mittagsseminar am 22.2.2015 heute, nicht 22.2. -- Helmut On 21.01.2015 18:51, Helmut Alt wrote: >> Im Rahmen des Mittagsseminars der >> Theoretischen Informatik der FU Berlin >> spricht am >> >> >> >> Donnerstag, 22.2.2015 >> Helmut Alt >> zum Thema: Weight Balancing on Boundaries and Skeletons >> >> >> *************************************************** >> Ort: Takustr. 9, RM 055 >> >> Uhrzeit: 12 Uhr s.t. >> *************************************************** >> > _______________________________________________ > agti-Mittagsseminar mailing list > agti-Mittagsseminar@lists.fu-berlin.de > https://lists.fu-berlin.de/listinfo/agti-mittagsseminar > > _______________________________________________ > Automatischer Mailverteiler an Gruppe 'ml-ti-mi'. > Hinweise dazu siehe Hilfeseite: > https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler ================================================================== Subject: Mittagsseminar am 22.2.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Donnerstag, 22.2.2015 Helmut Alt zum Thema: Weight Balancing on Boundaries and Skeletons *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar 20.01.2015 Morgen (Dienstag 20.01.2015) werde ich im Rahmen des Mittagsseminars der AGTI zum Thema *"Sets of points with even more perfect matchings"* sprechen. 12:00, T9/055 andrei ================================================================== Subject: Mittagsseminar am 13. u. 15.01.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 13.01.2015 Frank Hoffman zum Thema: Conflict-free Guarding: Another Lower Bound Proof und am Donnerstag, 15.01.2015 Katharina Klost zum Thema: Details on the integer sorting algorithm by Han and Thorup using O(n sqrt(log log n)) time and linear space (Bachelorvortrag) *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ================================================================== Subject: Mittagsseminar am 06.01.2015 Im Rahmen des Mittagsseminars der Theoretischen Informatik der FU Berlin spricht am Dienstag, 06.01.2015 Wolfgang Mulzer zum Thema: Time-Space Trade-offs for Voronoi diagrams *************************************************** Ort: Takustr. 9, RM 055 Uhrzeit: 12 Uhr s.t. *************************************************** ==================================================================