Mark Braverman
Abstract
We prove that poly-sized AC0 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 showed that O(log2 n)-independent distributions fool poly-size DNF formulas. [Razborov 2008] has later given a much simpler proof for Bazzi's theorem.
- Alon, N., Goldreich, O., and Mansour, Y. 2002. Almost k-wise independence versus k-wise independence. In Electronic Colloquium on Computational Complexity. Report TR02-048.Google Scholar
- Bazzi, L. M. J. 2007. Polylogarithmic independence can fool DNF formulas. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07). IEEE Computer Society Press, Los Alamitos, CA, 63--73. Google ScholarDigital Library
- Bazzi, L. M. J. 2009. Polylogarithmic independence can fool DNF formulas. SIAM J. Computing (SICOMP) 38, 6, 2220--2272. Google ScholarDigital Library
- Beigel, R. 1993. The polynomial method in circuit complexity. In Proceedings of the 8th IEEE Structure in Complexity Theory Conference. IEEE Computer Society Press, Los Alamitos, CA, 82--95.Google ScholarCross Ref
- Beigel, R., Reingold, N., and Spielman, D. 1991. The perceptron strikes back. In Proceedings of the 6th Annual Structure in Complexity Theory Conference. IEEE Computer Society Press, Los Alamitos, CA, 286--291.Google Scholar
- Håstad, J. 2001. A slight sharpening of LMN. J. Comput. Syst. Sci. 63, 3, 498--508.Google ScholarDigital Library
- Linial, N., Mansour, Y., and Nisan, N. 1993. Constant depth circuits, Fourier transform, and learnability. J. ACM 40, 3, 607--620. Google ScholarDigital Library
- Linial, N., and Nisan, N. 1990. Approximate inclusion-exclusion. Combinatorica 10, 4, 349--365.Google ScholarCross Ref
- Razborov, A. A. 1987. Lower bounds on the size of bounded-depth networks over a complete basis with logical addition. Math. Notes Acad. Sci. USSR 41, 4, 333--338.Google ScholarCross Ref
- Razborov, A. A. 2008. A simple proof of Bazzi's theorem. In Electronic Colloquium on Computational Complexity. Report TR08-081.Google Scholar
- Smolensky, R. 1987. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC'87). ACM New York, 77--82. Google ScholarDigital Library
- Tarui, J. 1993. Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy. Theoret. Comput. Sci. 113, 1, 167--183. Google ScholarDigital Library
- Valiant, L. G., and Vazirani, V. V. 1985. NP is as easy as detecting unique solutions. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC'85). ACM New York, 458--463. Google ScholarDigital Library
Index Terms
- Polylogarithmic independence fools AC0 circuits
Recommendations
Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of ComputingWe prove that if every problem in NP has nk-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 nO(k3)-size witness circuit: a witness for x that can ...
Poly-logarithmic Independence Fools AC^0 Circuits
CCC '09: Proceedings of the 2009 24th Annual IEEE Conference on Computational ComplexityWe prove that poly-sized AC^0 circuits cannot distinguish a poly-logarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [LN90]. The only prior progress on the problem was by Bazzi [Baz07], who ...
Tight Correlation Bounds for Circuits Between AC0 and TC0
CCC '23: Proceedings of the conference on Proceedings of the 38th Computational Complexity ConferenceWe initiate the study of generalized AC0 circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight ≥ k (up to negations of the input bits), which we denote GC0(k). The gate set of this class ...
Reviews
Bruce E. Litow
A probability distribution ? on {0,1} n ( n -dimensional hypercube) is said to be r -independent if every restriction of ? to r coordinates is uniform. As the author states, AC 0 circuits are circuits with AND , OR , and NOT gates, where the fan-in of the gates is unbounded. The principal objective of the paper is to show that a Boolean function F : {0,1} n ? {0,1} computed by a size ( m ) and depth ( d ) AC 0 circuit satisfies E ? ( F ) - E ( F ) < ? for any log ( m / ? ) O ( d 2)-independent distribution ? . Here, E ( F ) is the expected value of F under the uniform distribution on {0,1} n and E ? ( F ) is the expected value of F with regard to ? . The author points out an interesting consequence: namely, linear codes with polylog random seed length serve as pseudorandom generators for AC 0. This result extends the work of Bazzi [1] and Razborov [2]. The paper's main result is actually a corollary of its main technical result: Let F be as it is in the previous paragraph and let s ? m (this is a free sensitivity parameter that is cleverly used in the arguments). If r ? 3 ? 60 d +3 ? (log m )( d +1)( d +3) ? s d ( d +3), then E ? ( F ) - E ( F ) < 0.82 s ? (10 m ). The arguments employ interesting results on polynomial approximations to F . The paper is exceptionally clear, and it includes a wonderful graphic (Figure 1) that illustrates the correspondences among various approximating devices used in the proof of the main technical result. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments