We prove an average-case depth hierarchy theorem for Boolean
circuits over the standard basis of AND, OR, and NOT gates. Our
hierarchy theorem says that for every $d \geq 2$, there is an
explicit $n$-variable Boolean function $f$, computed by a...
What is the distribution of the number of triangles in the random
graph $G(n, 1/2)$? It was known for a long time that this
distribution obeys a central limit theorem: from the point of view
of large intervals (~ standard-deviation length), the...
The Resolution proof system is perhaps the simplest and most
universally used in verification system and automated theorem
proving. It was introduced by Davis and Putnam in 1960. The study
of its efficiency, both in terms of proof length of natural...
Tensor decompositions have been the key algorithmic components in
provable learning of a wide range of hidden variable models such as
topic models, Gaussian mixture models, independent component
analysis, dictionary learning. Despite its success...
Proof systems pervade all areas of mathematics (often in disguise:
e.g. Reidemeister moves is a sound and complete proof system for
proving the equivalence of knots given by their diagrams). Proof
complexity seeks to to understand the minimal...
The last few years have seen substantial progress on the question
of proving lower bounds for homogeneous depth-4 arithmetic
circuits. Even though these results seem to come close to resolving
the VP vs VNP question, it seems likely that the...
We prove that any algorithm for learning parities requires either a
memory of quadratic size or an exponential number of samples. This
proves a recent conjecture of Steinhardt, Valiant and Wager and
shows that for some learning problems a large...
Finding cliques in random graphs and the related planted variant
where one wants to recover an added clique of size $k$ added to a
random $G(n, 1/2)$ graph, have been extensively studied questions
in algorithm design. Despite intense effort, state...
The algorithm indicated in the title builds on Luks's classical
framework and introduces new group theoretic and combinatorial
tools. In the first talk we outline the algorithm and state the
core group theoretic and algorithmic ingredients. Some of...
The algorithm indicated in the title builds on Luks's classical
framework and introduces new group theoretic and combinatorial
tools. In the first talk we outline the algorithm and state the
core group theoretic and algorithmic ingredients. Some of...
