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