Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BOUNDED-DEPTH CIRCUITS:
Reports tagged with Bounded-depth Circuits:
TR03-013 | 7th March 2003
Luca Trevisan

#### An epsilon-Biased Generator in NC0

Cryan and Miltersen recently considered the question
of whether there can be a pseudorandom generator in
NC0, that is, a pseudorandom generator such that every
bit of the output depends on a constant number k of bits
of the seed. They show that for k=3 there ... more >>>

TR03-043 | 14th May 2003
Elchanan Mossel, Amir Shpilka, Luca Trevisan

#### On epsilon-Biased Generators in NC0

Cryan and Miltersen recently considered the question
of whether there can be a pseudorandom generator in
NC0, that is, a pseudorandom generator such that every
bit of the output depends on a constant number k of bits
of the seed. They show that for k=3 there is always a
distinguisher; ... more >>>

TR10-188 | 8th December 2010
Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich

#### Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae

Revisions: 1

We present a polynomial-time deterministic algorithm for testing whether constant-read multilinear arithmetic formulae are identically zero. In such a formula each variable occurs only a constant number of times and each subformula computes a multilinear polynomial. Our algorithm runs in time $s^{O(1)}\cdot n^{k^{O(k)}}$, where $s$ denotes the size of the ... more >>>

TR11-125 | 16th September 2011
Andrew Drucker