Computer Science and Discrete Mathematics (CSDM)

In this talk we will discuss some recent progress on some questions in extremal combinatorics and in multiparty communication complexity.

We will also discuss some general connections between the two fields, emphasizing how certain problems (e.g...

In 2023, Raghu Meka and I proved a substantially improved bound on the size of the smallest set of integers in [N] which contains no 3-term arithmetic progression. Since then, it has become clear that the main new ideas from that work are in fact...

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send the k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication? This is the...

A d-dimensional framework is a pair (G,p⃗ ) consisting of a finite simple graph G and an embedding p⃗  of its vertices in ℝd. A framework is called rigid if every continuous motion of the vertices in ℝd that starts at p⃗ , and preserves the lengths...

In quantum complexity theory, QMA and QCMA represent two different generalizations of NP. Both are defined as sets of languages whose Yes instances can be efficiently checked by a quantum verifier that is given a witness. With QMA the witness can be...

Expander graphs are a staple of theoretical computer science. These are graphs which are both sparse and well connected. They are simple to construct and modify. Therefore they are a central gadget in numerous applications in TCS and combinatorics...

A dot-product proof is a simple probabilistic proof system in which the verifier decides whether to accept an input vector based on a single linear combination of the entries of the input and a proof vector. I will present constructions of linear...

The Brunn-Minkowski inequality is a fundamental result in convex geometry controlling the volume of  the sum of subsets of ℝn. It asserts that for  sets A,B⊂ℝn of equal volume and a parameter t∈(0,1), we have |tA+(1−t)B|≥|A| with equality iff A=B is...

Tree decompositions, and in particular path decompositions, are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”...

The Brunn-Minkowski inequality is a fundamental result in convex geometry controlling the volume of  the sum of subsets of ℝn. It asserts that for  sets A,B⊂ℝn of equal volume and a parameter t∈(0,1), we have |tA+(1−t)B|≥|A| with equality iff A=B is...