Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials

Author Roei Tell



PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.13.pdf
  • Filesize: 0.95 MB
  • 48 pages

Document Identifiers

Author Details

Roei Tell

Cite AsGet BibTex

Roei Tell. Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 13:1-13:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.CCC.2017.13

Abstract

This work studies the question of quantified derandomization, which was introduced by Goldreich and Wigderson (STOC 2014). The generic quantified derandomization problem is the following: For a circuit class cal{C} and a parameter B=B(n), given a circuit C in cal{C} with n input bits, decide whether C rejects all of its inputs, or accepts all but B(n) of its inputs. In the current work we consider three settings for this question. In each setting, we bring closer the parameter setting for which we can unconditionally construct relatively fast quantified derandomization algorithms, and the "threshold" values (for the parameters) for which any quantified derandomization algorithm implies a similar algorithm for standard derandomization. For constant-depth circuits, we construct an algorithm for quantified derandomization that works for a parameter B(n) that is only slightly smaller than a "threshold" parameter, and is significantly faster than the best currently-known algorithms for standard derandomization. On the way to this result we establish a new derandomization of the switching lemma, which significantly improves on previous results when the width of the formula is small. For constant-depth circuits with parity gates, we lower a "threshold" of Goldreich and Wigderson from depth five to depth four, and construct algorithms for quantified derandomization of a remaining type of layered depth-3 circuit that they left as an open problem. We also consider the question of constructing hitting-set generators for multivariate polynomials over large fields that vanish rarely, and prove two lower bounds on the seed length of such generators. Several of our proofs rely on an interesting technique, which we call the randomized tests technique. Intuitively, a standard technique to deterministically find a "good" object is to construct a simple deterministic test that decides the set of good objects, and then "fool" that test using a pseudorandom generator. We show that a similar approach works also if the simple deterministic test is replaced with a distribution over simple tests, and demonstrate the benefits in using a distribution instead of a single test.
Keywords
  • Computational complexity
  • derandomization
  • quantified derandomization
  • hitting-set generator
  • constant-depth circuits

Metrics

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

References

  1. M. Bellare and J. Rompel. Randomness-efficient oblivious sampling. In \focs35th, pages 276-287, 1994. Google Scholar
  2. Andrej Bogdanov. Pseudorandom generators for low degree polynomials. In \stoc37th, pages 21-30. 2005. Google Scholar
  3. Andrej Bogdanov and Emanuele Viola. Pseudorandom bits for polynomials. \siamj, 39(6):2464-2486, 2010. Google Scholar
  4. Shiva Chaudhuri and Jaikumar Radhakrishnan. Deterministic restrictions in circuit complexity. In \stoc28th, pages 30-36, 1996. Google Scholar
  5. Kuan Cheng and Xin Li. Randomness extraction in AC0 and with small locality. \eccc, 23:18, 2016. Google Scholar
  6. Gil Cohen and Amnon Ta-Shma. Pseudorandom generators for low degree polynomials from algebraic geometry codes. \eccc, 20:155, 2013. Google Scholar
  7. Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. Improved pseudorandom generators for depth 2 circuits. In \rnd14th, pages 504-517, 2010. Google Scholar
  8. Oded Goldreich. Introduction to Property Testing (working draft), February 7, 2017. Accessed at http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html, February 14, 2017.
  9. Oded Goldreich and Avi Widgerson. On derandomizing algorithms that err extremely rarely. In \stoc46th, pages 109-118. 2014. Full version available online at \eccc, 20:152 (Rev. 2), 2013. Google Scholar
  10. Parikshit Gopalan, Raghu Meka, and Omer Reingold. Dnf sparsification and a faster deterministic counting algorithm. ç, 22(2):275-310, 2013. Google Scholar
  11. Johan Håstad. Computational Limitations of Small-depth Circuits. MIT Press, 1987. Google Scholar
  12. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: derandomizing the XOR lemma. In \stoc29th, pages 220-229. 1999. Google Scholar
  13. Swastik Kopparty and Srikanth Srinivasan. Certifying polynomials for AC^0[⊕] circuits, with applications. In \fsttcs32nd, pages 36-47. 2012. Google Scholar
  14. Shachar Lovett, Omer Reingold, Luca Trevisan, and Salil Vadhan. Pseudorandom bit generators that fool modular sums. In \rnd13th, pages 615-630. 2009. Google Scholar
  15. Noam Nisan and Avi Wigderson. Hardness vs. randomness. \jcss, 49(2):149-167, 1994. Google Scholar
  16. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  17. Alexander A. Razborov. Lower bounds on the size of constant-depth networks over a complete basis with logical addition. Mathematical Notes of the Academy of Science of the USSR, 41(4):333-338, 1987. Google Scholar
  18. Benjamin Rossman. The monotone complexity of k-clique on random graphs. \siamj, 43(1):256-279, 2014. Google Scholar
  19. Wolfgang M. Schmidt. Equations over Finite Fields: An Elementary Approach. Springer-Verlag Berlin, 1976. Google Scholar
  20. Avishay Tal. Tight bounds on the fourier spectrum of AC⁰. \eccc, 21:174, 2014. Google Scholar
  21. Roei Tell. Improved bounds for quantified derandomization of constant-depth circuits and polynomials. \eccc, 23, 2016. TR16-191. URL: https://eccc.weizmann.ac.il/report/2016/191/.
  22. Luca Trevisan. Extractors and pseudorandom generators. \jacm, 48(4):860-879, 2001. Google Scholar
  23. Luca Trevisan and TongKe Xue. A derandomized switching lemma and an improved derandomization of AC0. In çc28th, pages 242-247. 2013. Google Scholar
  24. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science. Now Publishers, 2012. Google Scholar
  25. Emanuele Viola. The sum of d small-bias generators fools polynomials of degree d. ç, 18(2):209-217, 2009. 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