slideshow 3

Complexity seminar

usually takes place each Friday at 13:30 in IM, rear building, ground floor
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.

Graphons as weak* limits

Jan Hladký
Friday, 19. January 2018 - 13:30 to 15:00

in IM, rear building, ground floor

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.

Prediction, partial information and hindsight

Navid Talebanfard
Friday, 12. January 2018 - 13:30 to 15:00

in IM, rear building, ground floor

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.

Quantum Adversary Bound

Alexander Belov
University of Latvia
Friday, 15. December 2017 - 13:30 to 15:00

in IM, rear building, ground floor

In this talk, I will briefly describe the quantum adversary bound, which is an intriguing way of characterising quantum query complexity, and sketch some of its applications. No prior knowledge of quantum computation is required.

Nested Convex Bodies are Chaseable

Martin Böhm
Friday, 24. November 2017 - 13:30 to 15:00

in IM, rear building, ground floor

In the Convex Body Chasing problem, we are given an initial point v in R^d and an online sequence of n convex bodies F_1,...,F_n. When we receive F_i, we are required to move inside F_i. Our goal is to minimize the total distance travelled. This fundamental online problem was first studied by Friedman and Linial (DCG 1993). They proved an Omega(sqrt(d)) lower bound on the competitive ratio, and conjectured that a competitive ratio depending only on d is possible. However, despite much interest in the problem, the conjecture remains wide open. In this work, we give a simple f(d)-competitive algorithm for chasing *nested* convex bodies in R^d, i.e. when F_2 lies inside F_1, F_3 lies inside F_2 and so on. Among other consequences, this indicates that the problem is considerably more difficult when the optimal path visits several points, as opposed to just moving to a single globally feasible position. Joint work with Nikhil Bansal, Marek Eliáš, Grigorios Koumoutsos, and... more