Document Open Access Logo

Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma

Authors Rocco A. Servedio, Li-Yang Tan

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.37.pdf
  • Filesize: 0.86 MB
  • 18 pages

Document Identifiers

Author Details

Rocco A. Servedio
  • Columbia University, New York, NY, USA
Li-Yang Tan
  • Stanford University, CA, USA

Funding

  • Servedio, Rocco A.: NSF grants CCF-1814873, IIS-1838154, CCF-1563155, and Simons Collaboration on Algorithms and Geometry.
  • Tan, Li-Yang: NSF CAREER award CCF-1942123.

Acknowledgements

This material is based upon work supported by the National Science Foundation under grant numbers listed above. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF).

Cite AsGet BibTex

Rocco A. Servedio and Li-Yang Tan. Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.37

Abstract

We study the problem of deterministically approximating the number of satisfying assignments of a polynomial threshold function (PTF) over Boolean space. We present and analyze a scheme for transforming such algorithms for PTFs over Gaussian space into algorithms for the more challenging and more standard setting of Boolean space. Applying this transformation to existing algorithms for Gaussian space leads to new algorithms for Boolean space that improve on prior state-of-the-art results due to Meka and Zuckerman [Meka and Zuckerman, 2013] and Kane [Kane, 2012]. Our approach is based on a bias-preserving derandomization of Meka and Zuckerman’s regularity lemma for polynomials [Meka and Zuckerman, 2013] using the [Rocco A. Servedio and Li-Yang Tan, 2018] pseudorandom generator for PTFs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Derandomization
  • Polynomial threshold functions
  • deterministic approximate counting

Metrics

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

References

  1. Noga Alon, Gregory Gutin, and Michael Krivelevich. Algorithms with large domination ratio. J. Algorithms, 50(1):118-134, 2004. Google Scholar
  2. Aline Bonami. Etude des coefficients Fourier des fonctiones de L^p(G). Ann. Inst. Fourier (Grenoble), 20(2):335-402, 1970. Google Scholar
  3. Anindya De, Ilias Diakonikolas, and Rocco A. Servedio. Deterministic approximate counting for juntas of degree-2 polynomial threshold functions. In Proceedings of the 29th Annual Conference on Computational Complexity (CCC), pages 229-240. IEEE, 2014. Google Scholar
  4. Anindya De and Rocco A. Servedio. Efficient deterministic approximate counting for low-degree polynomial threshold functions. In Proceedings of the 46th Annual Symposium on Theory of Computing (STOC), pages 832-841, 2014. Google Scholar
  5. Ilias Diakonikolas, Daniel M. Kane, and Jelani Nelson. Bounded independence fools degree-2 threshold functions. In Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS), pages 11-20, 2010. Google Scholar
  6. Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan. A regularity lemma and low-weight approximators for low-degree polynomial threshold functions. Theory of Computing, 10:27-53, 2014. Google Scholar
  7. Leonard Gross. Logarithmic Sobolev inequalities. Amer. J. Math., 97(4):1061-1083, 1975. Google Scholar
  8. Prahladh Harsha, Adam Klivans, and Raghu Meka. Bounding the sensitivity of polynomial threshold functions. Theory of Computing, 10(1):1-26, 2014. URL: http://www.theoryofcomputing.org/articles/v010a001.
  9. Valentine Kabanets, Daniel M Kane, and Zhenjian Lu. A polynomial restriction lemma with applications. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 615-628, 2017. Google Scholar
  10. Valentine Kabanets and Zhenjian Lu. Satisfiability and Derandomization for Small Polynomial Threshold Circuits. In Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM), volume 116, pages 46:1-46:19, 2018. Google Scholar
  11. Daniel Kane. k-independent Gaussians fool polynomial threshold functions. In Proceedings of the 26th Conference on Computational Complexity (CCC), pages 252-261, 2011. Google Scholar
  12. Daniel Kane. A small PRG for polynomial threshold functions of Gaussians. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 257-266, 2011. Google Scholar
  13. Daniel Kane. A structure theorem for poorly anticoncentrated Gaussian chaoses and applications to the study of polynomial threshold functions. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 91-100, 2012. Google Scholar
  14. Daniel Kane. A pseudorandom generator for polynomial threshold functions of Gaussians with subpolynomial seed length. In Proceedings of the 29th Annual Conference on Computational Complexity (CCC), pages 217-228, 2014. Google Scholar
  15. Daniel Kane. A polylogarithmic PRG for degree 2 threshold functions in the Gaussian setting. In Proceedings of the 30th Conference on Computational Complexity (CCC), pages 567-581, 2015. Google Scholar
  16. Daniel Kane and Raghu Meka. A PRG for Lipschitz functions of polynomials with applications to sparsest cut. In Proceedings of the 45th Annual Symposium on Theory of Computing (STOC), pages 1-10, 2013. Google Scholar
  17. Daniel Kane and Sankeerth Rao. A PRG for Boolean PTF of degree 2 with seed length subpolynomial in ε and logarithmic in n. In Proceedings of the 33rd Computational Complexity Conference (CCC), pages 2:1-2:24, 2018. Google Scholar
  18. Daniel M. Kane. The Correct Exponent for the Gotsman-Linial Conjecture. computational complexity, 23:151-175, 2014. Google Scholar
  19. Raghu Meka and David Zuckerman. Pseudorandom generators for polynomial threshold functions. SIAM Journal on Computing, 42(3):1275-1301, 2013. Google Scholar
  20. Elchannan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: Invariance and optimality. Annals of Mathematics, 171:295-341, 2010. Google Scholar
  21. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Available at URL: http://analysisofbooleanfunctions.net/.
  22. Ryan O'Donnell, Rocco A. Servedio, and Li-Yang Tan. Fooling Gaussian PTFs via Local Hyperconcentration. In Proceedings of the 51st Annual Symposium on Theory of Computing (STOC), 2020. to appear. Google Scholar
  23. Rocco A. Servedio and Li-Yang Tan. Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits. In Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM), pages 56:1-56:20, 2018. Google Scholar
  24. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 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 Imprint Privacy Contact