Document Open Access Logo

Pseudorandom Generators for Low Sensitivity Functions

Authors Pooya Hatami, Avishay Tal

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.29.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Pooya Hatami
Avishay Tal

Cite As Get BibTex

Pooya Hatami and Avishay Tal. Pseudorandom Generators for Low Sensitivity Functions. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.29

Abstract

A Boolean function is said to have maximal sensitivity s if s is the largest number of Hamming neighbors of a point which differ from it in function value.  We initiate the study of pseudorandom generators fooling low-sensitivity functions as an intermediate step towards settling the sensitivity conjecture. We construct a pseudorandom generator with seed-length 2^{O(s^{1/2})} log(n) that fools Boolean functions on n variables with maximal sensitivity at most s. Prior to our work, the (implicitly) best pseudorandom generators for this class of functions required seed-length 2^{O(s)} log(n).

Subject Classification

Keywords
  • Pseudorandom Generators
  • Sensitivity
  • Sensitivity Conjecture

Metrics

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

References

  1. M. Ajtai and A. Wigderson. Deterministic simulation of probabilistic constant depth circuits (preliminary version). In FOCS, pages 11-19, 1985. Google Scholar
  2. N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of algorithms, 7(4):567-583, 1986. Google Scholar
  3. N. Alon, O. Goldreich, J. Håstad, and R. Peralta. Simple construction of almost k-wise independent random variables. Random Structures and Algorithms, 3(3):289-304, 1992. Google Scholar
  4. Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, and Song Zuo. Tighter relations between sensitivity and other complexity measures. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 101-113. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_9.
  5. Louay M. J. Bazzi. Polylogarithmic independence can fool DNF formulas. SIAM J. Comput., 38(6):2220-2272, 2009. URL: http://dx.doi.org/10.1137/070691954.
  6. M. Braverman. Polylogarithmic independence fools AC⁰ circuits. J. ACM, 57(5):28:1-28:10, 2010. Google Scholar
  7. P. Gopalan, N. Nisan, R. A. Servedio, K. Talwar, and A. Wigderson. Smooth boolean functions are easy: Efficient algorithms for low-sensitivity functions. In ITCS, pages 59-70, 2016. Google Scholar
  8. Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, and Avi Wigderson. Degree and sensitivity: tails of two distributions. Electronic Colloquium on Computational Complexity (ECCC), 23:69, 2016. URL: http://eccc.hpi-web.de/report/2016/069.
  9. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 6-20. ACM, 1986. URL: http://dx.doi.org/10.1145/12130.12132.
  10. N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. Google Scholar
  11. N. Nisan and M. Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4:301-313, 1994. Google Scholar
  12. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. URL: http://dx.doi.org/10.1016/S0022-0000(05)80043-1.
  13. R. O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. Google Scholar
  14. Omer Reingold, Thomas Steinke, and Salil Vadhan. Pseudorandomness for regular branching programs via fourier analysis. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 655-670. Springer, 2013. Google Scholar
  15. H. U. Simon. A tight Ω(log log n)-bound on the time for parallel RAM’s to compute nondegenerated boolean functions. In Foundations of computation theory, pages 439-444. Springer, 1983. Google Scholar
  16. Avishay Tal. Tight bounds on the fourier spectrum of AC⁰. Electronic Colloquium on Computational Complexity (ECCC), 21:174, 2014. URL: http://eccc.hpi-web.de/report/2014/174.
  17. Luca Trevisan and Tongke Xue. A derandomized switching lemma and an improved derandomization of AC0. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pages 242-247. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/CCC.2013.32.
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