An interactive-PCP (say, for the membership x \in L) is a
proof that can be verified by reading only one of its bits, with the
help of a very short interactive-proof.
We show that for membership in some languages L, there are
interactive-PCPs that are significantly shorter than the known
more >>>
We give an explicit pseudorandom generator (PRG) for constant-depth read-once formulas over the basis \{\wedge, \vee, \neg\} with unbounded fan-in. The seed length of our PRG is \widetilde{O}(\log(n/\varepsilon)). Previously, PRGs with near-optimal seed length were known only for the depth-2 case (Gopalan et al. FOCS '12). For a constant depth ... more >>>
The Minimum Circuit Size Problem (MCSP) asks whether a (given) Boolean function has a circuit of at most a (given) size. Despite over a half-century of study, we know relatively little about the computational complexity of MCSP. We do know that questions about the complexity of MCSP have significant ramifications ... more >>>
There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The ``iterated restrictions'' approach, pioneered by Ajtai and Wigderson [AW89], has provided PRGs with seed length \mathrm{polylog} n or even \tilde{O}(\log n) for several restricted models of computation. Can this approach ever achieve the optimal seed ... more >>>
Attempts to prove the intractability of the Minimum Circuit Size Problem (MCSP) date as far back as the 1950s and are well-motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing MCSP is intractable under worst-case assumptions.
While ... more >>>