Computer Science and Discrete Mathematics (CSDM)

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 /...

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...

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...

Expander graphs are among the most useful objects in computer science and mathematics. They have found applications in numerous areas of both. I will review their definition, and explain some of the many applications. Time permitting, I will also...

Linear dynamical systems are a continuous subclass of reinforcement learning models that are widely used in robotics, finance, engineering, and meteorology. Classical control, since the work of Kalman, has focused on dynamics with Gaussian i.i.d...

Distributed learning protocols are designed to train on distributed data without gathering it all on a single centralized machine, thus contributing to the efficiency of the system and enhancing its privacy. We study a central problem in distributed...