We study the list-decodability of multiplicity codes.
These codes, which are based on evaluations of high-degree
polynomials and their derivatives, have rate approaching 1 while
simultaneously allowing for sublinear-time error-correction. In
this...
We present an iterative approach to constructing pseudorandom
generators, based on the repeated application of mild pseudorandom
restrictions. We use this template to construct pseudorandom
generators for combinatorial rectangles and read-once...
We study a new type of proof system, where an unbounded prover
and a polynomial time verifier interact, on inputs a string $x$ and
a function $f$, so that the Verifier may learn $f(x)$. The novelty
of our setting is that there no longer are ``good...
A basic fact of algebraic graph theory is that the number of
connected components in an undirected graph is equal to the
multiplicity of the eigenvalue zero in the Laplacian matrix of the
graph. In particular, the graph is disconnected if and only...
The problem of combinatorial auctions is one of the basic
questions in algorithmic mechanism design: how can we allocate/sell
m items to n agents with private valuations of different
combinations of items, so that the agents are motivated to...
I will talk about two natural notions of convergence for
sequences of graphs of bounded degree and their connection to
groups and group actions. The first is Benjamini-Schramm
convergence, which is strongly related to parameter testing. The
second...
The polynomial Freiman-Ruzsa conjecture is one of the important
open problems in additive combinatorics. In computer science, it
already has several diverse applications: explicit constructions of
two-source extractors; improved bounds for the log...
In joint work with Paul Valiant, we consider the tasks of
estimating a broad class of statistical properties, which includes
support size, entropy, and various distance metrics between pairs
of distributions. Our estimators are the first proposed...
In FT-mollification, one smooths a function while maintaining
good quantitative control on high-order derivatives. This is a
continuation of my talk from last week, and I will continue to
describe this approach and show how it can be used to show...
The braid group on n strands may be viewed as an infinite analog
of the symmetric group on n elements with additional topological
phenomena. It appears in several areas of mathematics, physics and
computer sciences, including knot theory...