Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NISAN-WIGDERSON GENERATOR:
Reports tagged with Nisan-Wigderson generator:
TR10-054 | 30th March 2010
Jan Krajicek

#### On the proof complexity of the Nisan-Wigderson generator based on a hard $NP \cap coNP$ function

Let $g$ be a map defined as the Nisan-Wigderson generator
but based on an $NP \cap coNP$-function $f$. Any string $b$ outside the range of
$g$ determines a propositional tautology $\tau(g)_b$ expressing this
fact. Razborov \cite{Raz03} has conjectured that if $f$ is hard on average for
P/poly then these ... more >>>

TR18-012 | 20th January 2018
Valentine Kabanets, Zhenjian Lu

#### Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates

We show how the classical Nisan-Wigderson (NW) generator [Nisan & Wigderson, 1994] yields a nontrivial pseudorandom generator (PRG) for circuits with sublinearly many polynomial threshold function (PTF) gates. For the special case of a single PTF of degree $d$ on $n$ inputs, our PRG for error $\epsilon$ has the seed ... more >>>

ISSN 1433-8092 | Imprint