We study the complexity of constructing a hitting set for the
class of polynomials that can be infinitesimally approximated by
polynomials that are computed by polynomial sized algebraic
circuits, over the real or complex numbers. Specifically, we...
It is classically understood how to learn the parameters of a
Gaussian even in high dimensions from independent samples. However,
estimators like the sample mean are very fragile to noise. In
particular, a single corrupted sample can arbitrarily...
Proof complexity studies the problem computer scientists and
mathematicians face every day: given a statement, how can we prove
it? A natural and well-studied question in proof complexity is to
find upper and lower bounds on the length of the...
A martingale is a sequence of random variables that maintain
their future expected value conditioned on the past. A
$[0,1]$-bounded martingale is said to polarize if it converges in
the limit to either $0$ or $1$ with probability $1$. A
martingale...
Geometric Complexity Theory (GCT) was developed by Mulmuley and
Sohoni as an approach towards the algebraic version of the P vs NP
problem, VP vs VNP, and, more generally, proving lower bounds on
arithmetic circuits. Exploiting symmetries, it...
We show that there exist binary locally testable codes (for all
rates) and locally correctable codes (for low rates) with rate and
distance approaching the Gilbert-Varshamov bound (which is the best
rate-distance tradeoff known for general binary...
Neural networks have been around for many decades. An important
question is what has led to their recent surge in performance and
popularity. I will start with an introduction to deep neural
networks, covering the terminology and standard approaches...
A theme that cuts across many domains of computer science and
mathematics is to find simple representations of complex
mathematical objects such as graphs, functions, or distributions on
data. These representations need to capture how the object...
A theme that cuts across many domains of computer science and
mathematics is to find simple representations of complex
mathematical objects such as graphs, functions, or distributions on
data. These representations need to capture how the object...
We present an explicit pseudorandom generator with seed length
$\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$
branching programs that can read their input bits in any order.
This improves upon the work of Impaggliazzo, Meka and...
