•  
    • Jan Hladký
    • (IM CAS)
    • Graphons as weak* limits
    • Abstract:
    • Around 2004, Lovasz and Szegedy came up with a certain compactification of the space of finite graphs. More precisely, they proved that there exists a metric - now called the cut-distance - which yields a compact topology. Their proof of compactnes relies on the Szemeredi regularity lemma. An entire theory, with applications in extremal graph theory and random graphs, developed from this statement. I will talk about approaching the cut-norm topology via the weak* topology. This approach gives a new view of many properties, and in particular yields a quick and elementary proof of the Lovasz-Szegedy theorem. The talk will be self-contained. Various bits of this are joint work with Martin Dolezal, Jan Grebik, Jon Noel, Diana Piguet, Israel Rocha, Vaclav Rozhon, Maria Saumell.
    • 19.01.18   13:30
    • Navid Talebanfard
    • (IM CAS)
    • Prediction, partial information and hindsight
    • Abstract:
    • Let X be a random variable distributed over n bit strings with entropy at least n - k. Subaddativity implies that the average coordinate has entropy close to 1 if k is small. Meir and Wigderson recently showed that the same remains true even if we are allowed to non-deterministically query around n/k other coordinates. I will present an alternative proof of this fact which quantitatively tightens this result. Furthermore I will show how Meir and Wigderson used to this to develop a top-down argument for depth-3 circuit lower bounds.  Based on join work with Alexander Smal.
    • 12.01.18   13:30

    Michal Koucky, Pavel Pudlak
    organizers

  •