Document Open Access Logo

Pseudorandomness and Fourier Growth Bounds for Width-3 Branching Programs

Authors Thomas Steinke, Salil Vadhan, Andrew Wan

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.885.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Thomas Steinke
Salil Vadhan
Andrew Wan

Cite As Get BibTex

Thomas Steinke, Salil Vadhan, and Andrew Wan. Pseudorandomness and Fourier Growth Bounds for Width-3 Branching Programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 885-899, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.885

Abstract

We present an explicit pseudorandom generator for oblivious, read-once, width-3 branching programs, which can read their input bits in any order. The generator has seed length O~( log^3 n ).
The previously best known seed length for this model is n^{1/2+o(1)} due to Impagliazzo, Meka, and Zuckerman (FOCS'12). Our work generalizes a recent result of Reingold, Steinke, and Vadhan (RANDOM'13) for permutation branching programs. The main technical novelty underlying our generator is a new bound on the Fourier growth of width-3, oblivious, read-once branching programs. Specifically, we show that for any f : {0,1}^n -> {0,1} computed by such a branching program, and k in [n], sum_{|s|=k} |hat{f}(s)| < n^2 * (O(\log n))^k,
where f(x) = sum_s hat{f}(s) (-1)^<s,x> is the standard Fourier transform over Z_2^n. The base O(log n) of the Fourier growth is tight up to a factor of log log n.

Subject Classification

Keywords
  • Pseudorandomness
  • Branching Programs
  • Discrete Fourier Analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Anil Ada, Omar Fawzi, and Hamed Hatami. Spectral norm of symmetric functions. In APPROX-RANDOM, pages 338-349. Springer, 2012. Google Scholar
  2. Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost k-wise independent random variables. In FOCS, pages 544-553, 1990. Google Scholar
  3. Michael Ben-Or and Nathan Linial. Collective coin flipping. Randomness and Computation, 5:91-115, 1990. Google Scholar
  4. Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff. Pseudorandomness for width 2 branching programs. ECCC, 16:70, 2009. Google Scholar
  5. Andrej Bogdanov, Periklis A. Papakonstantinou, and Andrew Wan. Pseudorandomness for read-once formulas. In FOCS, pages 240-246, 2011. Google Scholar
  6. Jean Bourgain. On the distribution of the fourier spectrum of boolean functions. Israel J. Mathematics, 131(1):269-276, 2002. Google Scholar
  7. Yigal Brandman, Alon Orlitsky, and John L. Hennessy. A spectral lower bound techniqye for the size of decision trees and two level and/or circuits. IEEE Transactions on Computers, 39(2):282-287, 1990. Google Scholar
  8. Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff. Pseudorandom generators for regular branching programs. FOCS, pages 40-47, 2010. Google Scholar
  9. Joshua Brody and Elad Verbin. The coin problem and pseudorandomness for branching programs. In FOCS, pages 30-39, 2010. Google Scholar
  10. Jehoshua Bruck. Harmonic analysis of polynomial threshold functions. SIAM J. Discrete Mathematics, 3:168-177, 1990. Google Scholar
  11. Jehoshua Bruck and Roman Smolensky. Polynomial threshold functions, AC⁰ functions, and spectral norms. SIAM J. Computing, 21(1):33-42, 1992. Google Scholar
  12. L. Elisa Celis, Omer Reingold, Gil Segev, and Udi Wieder. Balls and bins: Smaller hash families and faster evaluation. In FOCS, pages 599-608, 2011. Google Scholar
  13. Anindya De. Pseudorandomness for permutation and regular branching programs. In CCC, pages 221-231, 2011. Google Scholar
  14. Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. Improved pseudorandom generators for depth 2 circuits. In Maria Serna, Ronen Shaltiel, Klaus Jansen, and José Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, volume 6302 of Lecture Notes in Computer Science, pages 504-517. Springer, 2010. Google Scholar
  15. Lars Engebretsen, Piotr Indyk, and Ryan O'Donnell. Derandomized dimensionality reduction with applications. In SODA, pages 705-712, 2002. Google Scholar
  16. Ehud Friedgut. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27-35, 1998. Google Scholar
  17. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan. Better pseudorandom generators from milder pseudorandom restrictions. In FOCS, pages 120-129, 2012. Google Scholar
  18. Ben Green and Tom Sanders. Boolean functions with small spectral norm. Geometric and Functional Analysis, 18(1):144-162, 2008. Google Scholar
  19. Vince Grolmusz. On the power of circuits with gates of low 𝓁₁ norms. Theoretical computer science, 188(1):117-128, 1997. Google Scholar
  20. Iftach Haitner, Danny Harnik, and Omer Reingold. On the power of the randomized iterate. In CRYPTO, 2006. Google Scholar
  21. Alexander Healy, Salil Vadhan, and Emanuele Viola. Using nondeterminism to amplify hardness. SIAM J. Computing, 35(4):903-931 (electronic), 2006. Google Scholar
  22. R. Impagliazzo, R. Meka, and D. Zuckerman. Pseudorandomness from shrinkage. In FOCS, pages 111-119, 2012. Google Scholar
  23. Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In STOC, pages 356-364, 1994. Google Scholar
  24. Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM, 53(3):307-323, 2006. Google Scholar
  25. Eyal Kaplan, Moni Naor, and Omer Reingold. Derandomized constructions of k-wise (almost) independent permutations. In APPROX-RANDOM, pages 354-365, 2005. Google Scholar
  26. Michal Koucký, Prajakta Nimbhorkar, and Pavel Pudlák. Pseudorandom generators for group products. In STOC, pages 263-272, 2011. Google Scholar
  27. Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM J. Computing, 22(6):1331-1348, 1993. Google Scholar
  28. Yishay Mansour. An O (n log log n) learning algorithm for DNF under the uniform distribution. J. CSS, 50(3):543-550, 1995. Google Scholar
  29. Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM J. Computing, 22:838-856, 1993. Google Scholar
  30. Noam Nisan. RL ⊂ SC. In STOC, pages 619-623, 1992. Google Scholar
  31. Noam Nisan and David Zuckerman. More deterministic simulation in logspace. In STOC, pages 235-244, 1993. Google Scholar
  32. Omer Reingold, Thomas Steinke, and Salil Vadhan. Pseudorandomness for regular branching programs via fourier analysis. In APPROX-RANDOM, pages 655-670, 2013. Google Scholar
  33. Michael Saks and Shiyu Zhou. BP_HSPACE(S) ⊂ DSPACE(S^3/2). J. CSS, 58(2):376-403, 1999. Google Scholar
  34. Amir Shpilka, Avishay Tal, et al. On the structure of boolean functions with small spectral norm. In ITCS, pages 37-48, 2014. Google Scholar
  35. D. Sivakumar. Algorithmic derandomization via complexity theory. In CCC, page 10, 2002. Google Scholar
  36. John Steinberger. The distinguishability of product distributions by read-once branching programs. In CCC, pages 248-254, 2013. Google Scholar
  37. Thomas Steinke. Pseudorandomness for permutation branching programs without the group theory. ECCC, 19:83, 2012. Google Scholar
  38. Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang. Fourier sparsity, spectral norm, and the log-rank conjecture. In FOCS, pages 658-667, 2013. Google Scholar
  39. Jiří Šíma and Stanislav Žák. A sufficient condition for sets hitting the class of read-once branching programs of width 3. In SOFSEM, pages 406-418, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact