Nisan-Wigderson generator can be computed in $\log^{O(1)} n$ space and fools all constant-depth circuits of size poly($n$). I mean Theorem 5 here.

I want another generator, that can be computed in poly($n$) space (but stil it is a function $\{0,1\}^l \to \{0,1\}^n$, where $l = \log^{O(1)} n$ ) however can fool more powerful circuits.

Do such generators exist (unconditional to assumptions)?

  • 6
    $\begingroup$ I'm reasonably sure that you can unconditionally fool all poly-size circuits with those assumptions. You are allowing yourself PSPACE-level computational power, which means you can implement non-constructive probabilistic method existence proofs of pseudorandom generators. i.e. your PRG is the lexicographically first function that satisfies the PRG condition for poly size circuits, which can be evaluated in polynomial space. $\endgroup$ – Thomas Feb 27 '17 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.