Monday, November 7, 2016
Freie Universität Berlin
Institut für Informatik
Lecture - 14:15
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
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.