Error correcting codes are objects designed to withstand errors
that may arise during communication. Originally intended for
practical use, codes have come to be established as one of the
central objects of study in theoretical computer science,
due...
Every word in a free group induces a probability distribution on
every finite group by substituting the letters of w by uniformly
random elements of the group. The connection between such
distributions on the symmetric group and the poset of...
What can be said about a system of polynomial equations over a
finite field if its number of solutions deviates from that of a
random system? Answer: Roughly, one of the polynomials (or a linear
combination thereof) can be written in terms of “few”...
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...
