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...
In 1964 Arnold constructed an example of instabilities for
nearly integrable systems and conjectured that generically this
phenomenon takes place.
There has been big progress attacking this conjecture in the past
decade. Jointly with Ke Zhang we...
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...
We describe some results concerning the number of connected
components of nodal lines of high frequency Maass forms on the
modular surface. Based on heuristics connecting these to a critical
percolation model, Bogomolny and Schmit have conjectured...
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...
My goal in this talk is to survey some of the emerging
applications of polynomial methods in both learning and in
statistics. I will give two examples from my own work in which the
solution to well-studied problems in learning and statistics
can...
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...
We explain in this talk how Ramanujan graphs can be used to
devise optimal cycle codes and review how other graph families
related to a construction proposed by Margulis yield interesting
families of quantum codes with logarithmic minimum distance...
The history of digital computing can be divided into an Old
Testament whose prophets, led by Gottfried Wilhelm Leibniz,
supplied the logic, and a New Testament whose prophets, led by John
von Neumann, built the machines. Alan Turing, whose “On...
