Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, November 7, 2016

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

Amin Coja-Oghlan - Goethe-Universität Frankfurt a/M

Information-theoretic thresholds from the cavity method

Physicists have put forward predictions on the information-theoretic thresholds in inference problems such as maximum likelihood decoding. Their deliberations rely on a non-rigorous but analytic approach called the cavity method. The talk is about a new rigorous technique that vindicates the physics predictions for a wide variety of problems.

Colloquium - 16:00

Piotr Micek - FU Berlin & Jagellonian Univ., Krakow

Nonrepetitive colorings and entropy compression method

A sequence is nonrepetitive if it does not contain two adjacent identical blocks. The remarkable construction of Thue asserts that 3 symbols are enough to build an arbitrarily long nonrepetitive sequence. It is still not settled whether the following extension holds: for every sequence of 3-element sets L1, . . . , Ln there exists a nonrepetitive sequence s1, . . . , sn with si in Li, for every i. We propose a new non-constructive way to build long nonrepetitive sequences and provide an elementary proof that sets of size 4 suffice confirming the best known bound. We discuss the recent progress on nonrepetitive colorings of graphs.
Joint work with Jaroslaw Grytczuk and Jakub Kozik.

Letzte Aktualisierung: 04.11.2016