Computer Science and Discrete Mathematics (CSDM)

Determining the complexity of matrix multiplication is a fundamental problem of theoretical computer science. It is popularly conjectured that matrices can be multiplied in nearly-linear time. If true, this conjecture would yield similarly-fast...

A Locally Decodable Codes (LDC) is an error correcting code which allows the decoding of a single message symbol from a few queries to a possibly corrupted encoding.  LDCs can be constructed, for example, from low degree polynomials over a finite...

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