Computer Science and Discrete Mathematics (CSDM)

Over a high-dimensional vector space Fnpover a fixed finite field Fp, the inverse theorem for the Gowers norm asserts that a bounded function f on this space that has a large Gowers Uk+1 norm, must necessarily correlate with a phase polynomial e(P)...

A seminal result in learning theory characterizes the PAC learnability of binary classes through the VC dimension. Extending this characterization to the general multiclass setting has been open since the late 1980s.

We resolve this problem by...

Our goal is to develop a generic framework for converting modern gradient-descent based optimization algorithms into mechanisms where inputs come from self-interested agents.

We focus on aggregating preferences from n players in a context...

The online list labeling problem is a basic primitive in data structures. The goal is to store a dynamically-changing set of n items in an array of m slots, while keeping the elements in sorted order. To do so, some items may need to be moved over...

The classic algorithm AdaBoost allows to convert a weak learner, that is an algorithm that produces a hypothesis which is slightly better than chance, into a strong learner, achieving arbitrarily high accuracy when given enough training data. We...

The recently-discoverd Hypergraph Container Method (Saxton and Thomason, Balogh, Morris and Samotij), generalizing an earlier version for graphs (Kleitman and Winston), is used extensively in recent years in extremal and probabilistic combinatroics...

Sampling from high-dimensional, multimodal distributions is a computationally challenging and fundamental task.  This talk will focus on a family of random instances of such problems described by random quadratic potentials on the hypercube known as...

A powerful technique developed and extended in the past decade in communication complexity is the so-called "lifting theorems."  The idea is to translate the hardness results from "easier" models, e.g., query complexity, polynomial degrees, to the...

In this talk, we show a strong XOR lemma for bounded-round two-player randomized communication.  For a function f:X×Y→{0,1}, the n-fold XOR function f^⊕n:X^n×Y^n→{0,1} maps n input pairs (x_1,...,x_n), (y_1,...,y_n) to the XOR of the n output bits f...

In this talk I will first review some basics about communication complexity.  Secondly I will survey some (old and new) equivalences between central problems in communication complexity and related questions in additive combinatorics.  In particular...