
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 cutdistance  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 cutnorm 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 LovaszSzegedy theorem.
The talk will be selfcontained. Various bits of this are joint work with Martin Dolezal, Jan Grebik,
Jon Noel, Diana Piguet, Israel Rocha, Vaclav Rozhon, Maria Saumell.

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
nondeterministically 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 topdown argument for depth3 circuit lower
bounds.
Based on join work with Alexander Smal.
Michal Koucky, Pavel Pudlak
organizers