2020-21 Seminars

Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets in a (possibly higher...

We introduce two new notions for polynomials associated with discrete set-valued probability distributions. These notions generalize well-studied properties like real-stability and log-concavity, but unlike them robustly degrade under a number of...

We will talk about a recent result of Jeff Kahn, Bhargav Narayanan, and myself stating that the threshold for the random graph G(n,p) to contain the square of a Hamilton cycle is 1/sqrt n, resolving a conjecture of Kühn and Osthus from 2012. For...

We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel t times is at most $t^{-\Omega(1)}. Previously, only a bound of roughly 1 /...

The talk will be an introduction and a road map to the various connections the topic has with other areas of math and CS.

How dense can a set of integers be while containing no three-term arithmetic progressions? This is one of the classical problems of additive combinatorics, and since the theorem of Roth in 1953 that such a set must have zero density, there has been...

In this talk I will introduce constructions of finite graphs which resemble some given infinite graph both in terms of their local neighborhoods, and also their spectrum. These graphs can be thought of as expander graphs with local constraints in a...

In this talk I will first motivate lifting theorems where lower bounds on communication complexity for composed functions are obtained by a general simulation theorem, essentially showing that no protocol can do any better than the obvious "query"...

It is known that any opened necklace with beads of n types can be partitioned by at most (k-1)n cuts into intervals that can be distributed into k collections, each containing the same number of beads of each type (up to 1). The proof is topological...