Article

Improved pseudorandom generators for depth 2 circuits

Authors:

Madhur TulsianiAuthors Info & Claims

APPROX/RANDOM'10: Proceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques

Pages 504 - 517

Published: 01 September 2010 Publication History

Abstract

We prove the existence of a poly(n,m)-time computable pseudorandom generator which "1/poly(n,m)-fools" DNFs with n variables and m terms, and has seed length O(log²nm ċ log log nm). Previously, the best pseudorandom generator for depth-2 circuits had seed length O(log³ nm), and was due to Bazzi (FOCS 2007).

It follows from our proof that a 1/m^{Õ(log mn)}-biased distribution 1/poly(nm)-fools DNFs with m terms and n variables. For inverse polynomial distinguishing probability this is nearly tight because we show that for every m, δ there is a 1/m^{Ω(log 1/δ)}-biased distribution X and a DNF φ with m terms such that φ is not δ-fooled by X.

For the case of read-once DNFs, we show that seed length O(log mn ċ log 1/δ) suffices, which is an improvement for large δ.

It also follows from our proof that a 1/m^{O(log 1/δ)}-biased distribution δ-fools all read-once DNF with m terms. We show that this result too is nearly tight, by constructing a 1/m^{Ω(log 1/δ)}-biased distribution that does not δ-fool a certain m-term read-once DNF.

References

[1]

Ajtai, M., Wigderson, A.: Deterministic simulation of probabilistic constand-depth circuits. Advances in Computing Research - Randomness and Computation 5, 199- 223 (1989); Preliminary version in Proc. of FOCS 1985.

Digital Library

[2]

Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Structures and Algorithms 3(3), 289-304 (1992).

[3]

Alon, N., Goldreich, O., Mansour, Y.: Almost k-wise independence versus k-wise independence. Information Processing Letters 88(3), 107-110 (2003).

Digital Library

[4]

Bazzi, L.: Minimum Distance of Error Correcting Codes versus Encoding Complexity, Symmetry, and Pseudorandomness. PhD thesis, MIT (2003).

Digital Library

[5]

Bazzi, L.: Polylogarithmic independence can fool DNF formulas. In: Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, pp. 63-73 (2007).

Digital Library

[6]

Braverman, M.: Poly-logarithmic independence fools AC⁰ circuits. In: Proceedings of the 24th IEEE Conference on Computational Complexity, pp. 3-8 (2009).

Digital Library

[7]

Even, G., Goldreich, O., Luby, M., Nisan, N., Velickovic, B.: Approximations of general independent distributions. In: Proceedings of the 24th ACM Symposium on Theory of Computing, pp. 10-16 (1992).

Digital Library

[8]

Håstad, J.: Almost optimal lower bounds for small depth circuits. In: Proceedings of the 18th ACM Symposium on Theory of Computing, pp. 6-20 (1986).

Digital Library

[9]

Klivans, A., Lee, H., Wan, A.: Mansour's conjecture is true for random DNF formulas. Technical Report TR10-023, Electronic Colloquium on Computational Complexity (2010).

[10]

Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, fourier transform and learnability. Journal of the ACM 40(3), 607-620 (1993).

Digital Library

[11]

Linial, N., Nisan, N.: Approximate inclusion-exclusion. Combinatorica 10(4), 349- 365 (1990).

[12]

Luby, M., Velickovic, B.: On deterministic approximation of DNF. Algorithmica 16(4/5), 415-433 (1996).

[13]

Luby, M., Velickovic, B., Wigderson, A.: Deterministic approximate counting of depth-2 circuits. In: Proceedings of the 2nd ISTCS, pp. 18-24 (1993).

[14]

Mak, L.: Parallelism always helps. Manuscript (1993).

[15]

Mansour, Y.: An o(n ^{log log n)} learning algorithm for DNF under the uniform distribution. Journal of Computer and System Sciences 50(3), 543-550 (1995).

Digital Library

[16]

Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM Journal on Computing 22(4), 838-856 (1993).

Digital Library

[17]

Nisan, N.: Pseudorandom bits for constant depth circuits. Combinatorica 12(4), 63-70 (1991).

[18]

O'Donnell, R.: Lecture notes for analysis of boolean functions (2007), http://www.cs.cmu.edu/~odonnell/boolean-analysis

[19]

Razborov, A.: A Simple Proof of Bazzi's Theorem. ACM Trans. Comput. Theory 1(1), 1-5 (2009).

Digital Library

[20]

Viola, E., Wigderson, A.: Norms, XOR lemmas, and lower bounds for polynomials and protocols. Theory of Computing 4(1), 137-168 (2008).

Cited By

Chen XChan T(2019)Derandomized balanced allocationProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310589(2513-2526)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310589
Servedio RTan LChan T(2019)Pseudorandomness for read-k DNF formulasProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310474(621-638)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310474
Tal A(2017)Tight bounds on the Fourier spectrum of AC0Proceedings of the 32nd Computational Complexity Conference10.5555/3135595.3135610(1-31)Online publication date: 9-Jul-2017
https://dl.acm.org/doi/10.5555/3135595.3135610
Show More Cited By

Improved pseudorandom generators for depth 2 circuits
1. Theory of computation

Recommendations

Near-optimal pseudorandom generators for constant-depth read-once formulas
CCC '19: Proceedings of the 34th Computational Complexity Conference

We give an explicit pseudorandom generator (PRG) for read-once AC⁰, i.e., constant-depth read-once formulas over the basis [EQUATION] with unbounded fan-in. The seed length of our PRG is Õ(log(n/ε)). Previously, PRGs with near-optimal seed length were ...
Improved pseudorandom generators for AC⁰ circuits
CCC '22: Proceedings of the 37th Computational Complexity Conference

We give PRG for depth-d, size-m AC⁰ circuits with seed length O(log^d−1 (m) log(m/ε) log log(m)). Our PRG improves on previous work [27, 25, 18] from various aspects. It has optimal dependence on 1/ε and is only one "log log(m)" away from the lower bound ...
Pseudorandom Generators with Optimal Seed Length for Non-Boolean Poly-Size Circuits

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

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

APPROX/RANDOM'10: Proceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques

September 2010

781 pages

ISBN:3642153682

Editors:
Maria Serna
Universitat Politècnica de Catalunya, Dept. de Llenguatges i Sistemes Informàtics, Barcelona, Spain
,
Ronen Shaltiel
University of Haifa, Department of Computer Science, Haifa, Israel
,
Klaus Jansen
University of Kiel, Department of Computer Science, Kiel, Germany
,
José Rolim
University of Geneva, Centre Universitaire d'Informatique, Carouge, Switzerland

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 September 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen XChan T(2019)Derandomized balanced allocationProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310589(2513-2526)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310589
Servedio RTan LChan T(2019)Pseudorandomness for read-k DNF formulasProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310474(621-638)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310474
Tal A(2017)Tight bounds on the Fourier spectrum of AC0Proceedings of the 32nd Computational Complexity Conference10.5555/3135595.3135610(1-31)Online publication date: 9-Jul-2017
https://dl.acm.org/doi/10.5555/3135595.3135610
Tell R(2017)Improved bounds for quantified derandomization of constant-depth circuits and polynomialsProceedings of the 32nd Computational Complexity Conference10.5555/3135595.3135608(1-48)Online publication date: 9-Jul-2017
https://dl.acm.org/doi/10.5555/3135595.3135608
Bazzi LNahas N(2017)Small-Bias is Not Enough to Hit Read-Once CNFTheory of Computing Systems10.1007/s00224-016-9680-660:2(324-345)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s00224-016-9680-6
Kane DWatanabe O(2016)A Short Implicant of a CNF Formula with Many Satisfying AssignmentsAlgorithmica10.1007/s00453-016-0125-z76:4(1203-1223)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s00453-016-0125-z
Goldreich OWidgerson AShmoys D(2014)On derandomizing algorithms that err extremely rarelyProceedings of the forty-sixth annual ACM symposium on Theory of computing10.1145/2591796.2591808(109-118)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2591796.2591808
Šíma JŽák S(2012)A sufficient condition for sets hitting the class of read-once branching programs of width 3Proceedings of the 38th international conference on Current Trends in Theory and Practice of Computer Science10.1007/978-3-642-27660-6_33(406-418)Online publication date: 21-Jan-2012
https://dl.acm.org/doi/10.1007/978-3-642-27660-6_33
O'Donnell RWright JZhou Y(2011)The Fourier entropy-influence conjecture for certain classes of Boolean functionsProceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I10.5555/2027127.2027162(330-341)Online publication date: 4-Jul-2011
https://dl.acm.org/doi/10.5555/2027127.2027162

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents