The problem of learning arithmetic circuits is the following:
given a polynomial as a black box that is promised to have a small
arithmetic circuit computing it, can we find this arithmetic
circuit? This problem is hard in the worst case and so...
In this second lecture in my series on asymptotic spectra we
will focus on one application: the matrix multiplication problem.
We will use the asymptotic spectrum of tensors to prove that a very
general method (that includes the methods used to...
The choiceless computation model of Blass, Gurevich and Shelah
(1999, 2002) is an algorithmic framework for computing
isomorphism-invariant properties of unordered structures. Machines
in this model have the power of parallel execution, but lack...
The first lecture in this series is an introduction to the
theory of asymptotic spectra. This theory describes asymptotic
behavior of basic objects in mathematics like graphs and tensors.
Example applications that we will see are the matrix...
A sunflower with $r$ petals is a collection of $r$ sets so that
the intersection of each pair is equal to the intersection of all.
Erdos and Rado in 1960 proved the sunflower lemma: for any fixed
$r$, any family of sets of size $w$, with at least...
Worst-case analysis of algorithms has been the central method of
theoretical computer science for the last 60 years, leading to
great discoveries in algorithm design and a beautiful theory of
computational hardness. However, worst-case analysis...
The seminal result of Kahn, Kalai and Linial implies that a
coalition of a small number of players can bias the outcome of a
Boolean function with respect to the uniform measure. We extend
this result to arbitrary product measures, by combining...
We give a pseudorandom generator that fools $m$-facet polytopes
over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot
\mathrm{log}(n)$. The previous best seed length had superlinear
dependence on $m$. An immediate consequence is a...
Are factors of sparse polynomials sparse? This is a really basic
question and we are still quite far from understanding it in
general. In this talk, I will discuss a recent result showing that
this is in some sense true for multivariate polynomials...
Constraint satisfaction problems (CSPs) are a central topic of
study in computer science. A fundamental question about CSPs is as
follows. Given a CSP where each constraint has the form of some
predicate P and almost all of the constraints can be...
