Poly-logarithmic Independence Fools AC^0 Circuits

We prove that poly-sized AC⁰ circuits cannot distinguish a polylogarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [1990]. The only prior progress on the problem was by Bazzi [2007], who ...

We prove that if every problem in NP has n^k-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier’s search space has an n^O(k3)-size witness circuit: a witness for x that can ...

A sampling procedure for a distribution P over {0, 1}^ℓ is a function C: {0, 1}ⁿ → {0, 1}^ℓ such that the distribution C(U_n) (obtained by applying C on the uniform distribution U_n) is the “desired distribution” P. Let n > r ≥ ℓ = n^Ω(1). An ϵ-nb-PRG (...