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 <marehr@zedat.fu-berlin.de>
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 <mulzer@inf.fu-berlin.de>
To: agti-Mittagsseminar@lists.fu-berlin.de
CC: Fr=C3=A9d=C3=A9ric Meunier <frederic.meunier@enpc.fr>
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 <alexander.kauer@fu-berlin.de>
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 <lilian.hung@fu-berlin.de>
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.
***************************************************
==================================================================