Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with constant depth formulas:
TR07-031 | 26th March 2007
Yael Tauman Kalai, Ran Raz

Interactive PCP

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 >>>

TR18-183 | 5th November 2018
Dean Doron, Pooya Hatami, William Hoza

Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

Revisions: 2

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 >>>

TR19-021 | 19th February 2019
Rahul Ilango

$AC^0[p]$ Lower Bounds and NP-Hardness for Variants of MCSP

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 >>>

ISSN 1433-8092 | Imprint