Jan Krajicek

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