Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CONSTANT DEPTH CIRCUIT:
Reports tagged with constant depth circuit:
TR04-020 | 8th March 2004
Emanuele Viola

#### The Complexity of Constructing Pseudorandom Generators from Hard Functions

We study the complexity of building
pseudorandom generators (PRGs) from hard functions.

We show that, starting from a function f : {0,1}^l -> {0,1} that
is mildly hard on average, i.e. every circuit of size 2^Omega(l)
fails to compute f on at least a 1/poly(l)
fraction of inputs, we can ... more >>>

TR04-074 | 26th August 2004
Emanuele Viola

#### On Parallel Pseudorandom Generators

Revisions: 1

We study pseudorandom generator (PRG) constructions $G^f : {0,1}^l \to {0,1}^{l+s}$ from one-way functions $f : {0,1}^n \to {0,1}^m$. We consider PRG constructions of the form $G^f(x) = C(f(q_{1}) \ldots f(q_{poly(n)}))$
where $C$ is a polynomial-size constant depth circuit
and $C$ and the $q$'s are generated from $x$ arbitrarily.
more >>>

TR21-018 | 20th February 2021
Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan

#### Monotone Branching Programs: Pseudorandomness and Circuit Complexity

We study monotone branching programs, wherein the states at each time step can be ordered so that edges with the same labels never cross each other. Equivalently, for each fixed input, the transition functions are a monotone function of the state.

We prove that constant-width monotone branching programs of ... more >>>

ISSN 1433-8092 | Imprint