Document Open Access Logo

Sampling and Certifying Symmetric Functions

Authors Yuval Filmus , Itai Leigh , Artur Riazanov , Dmitry Sokolov

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2023.36.pdf
  • Filesize: 0.9 MB
  • 21 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Generating random combinatorial structures
Keywords
  • sampling
  • lower bounds
  • robust sunflowers
  • decision trees
  • switching networks

Metrics

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

Abstract

A circuit 𝒞 samples a distribution X with an error ε if the statistical distance between the output of 𝒞 on the uniform input and X is ε. We study the hardness of sampling a uniform distribution over the set of n-bit strings of Hamming weight k denoted by Uⁿ_k for decision forests, i.e. every output bit is computed as a decision tree of the inputs. For every k there is an O(log n)-depth decision forest sampling Uⁿ_k with an inverse-polynomial error [Emanuele Viola, 2012; Czumaj, 2015]. We show that for every ε > 0 there exists τ such that for decision depth τ log (n/k) / log log (n/k), the error for sampling U_kⁿ is at least 1-ε. Our result is based on the recent robust sunflower lemma [Ryan Alweiss et al., 2021; Rao, 2019].
Our second result is about matching a set of n-bit strings with the image of a d-local circuit, i.e. such that each output bit depends on at most d input bits. We study the set of all n-bit strings whose Hamming weight is at least n/2. We improve the previously known locality lower bound from Ω(log^* n) [Beyersdorff et al., 2013] to Ω(√log n), leaving only a quartic gap from the best upper bound of O(log² n).

Cite As Get BibTex

Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov. Sampling and Certifying Symmetric Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.36

Author Details

Yuval Filmus
  • Technion - Israel Institute of Technology, Haifa, Israel
Itai Leigh
  • Tel-Aviv University, Israel
Artur Riazanov
  • École Polytechnique Fédérale de Lausanne, Switzerland
Dmitry Sokolov
  • École Polytechnique Fédérale de Lausanne, Switzerland

Funding

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 802020-ERC-HARMONIC. This work was supported by the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number MB22.00026.

Acknowledgements

We thank Mika Göös, Aleksandr Smal, and Anastasia Sofronova for fruitful discussions and suggestions. We thank the RANDOM 2023 anonymous referees for their helpful comments.

References

  1. Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Improved bounds for the sunflower lemma. Annals of Mathematics, 194(3):795-815, 2021. URL: https://doi.org/10.4007/annals.2021.194.3.5.
  2. Lászió Babai. Random oracles separate pspace from the polynomial-time hierarchy. Information Processing Letters, 26(1):51-53, 1987. URL: https://doi.org/10.1016/0020-0190(87)90036-6.
  3. Chris Beck, Russell Impagliazzo, and Shachar Lovett. Large deviation bounds for decision trees and sampling lower bounds for ac0-circuits. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 101-110, 2012. URL: https://doi.org/10.1109/FOCS.2012.82.
  4. Tolson Bell, Suchakree Chueluecha, and Lutz Warnke. Note on sunflowers. Discrete Mathematics, 344(7):112367, 2021. URL: https://doi.org/10.1016/j.disc.2021.112367.
  5. Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, and Heribert Vollmer. Verifying proofs in constant depth. ACM Trans. Comput. Theory, 5(1):Art. 2, 23, 2013. URL: https://doi.org/10.1145/2462896.2462898.
  6. Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan. Bounded indistinguishability for simple sources. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 26:1-26:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.26.
  7. Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson. Bounded indistinguishability and the complexity of recovering secrets. In Advances in Cryptology - CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part III, pages 593-618. Springer, 2016. Google Scholar
  8. Eshan Chattopadhyay, Jesse Goodman, and David Zuckerman. The Space Complexity of Sampling. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1-40:23, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.40.
  9. Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 670-683, 2016. Google Scholar
  10. Gil Cohen and Leonard J Schulman. Extractors for near logarithmic min-entropy. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 178-187. IEEE, 2016. Google Scholar
  11. Artur Czumaj. Random permutations using switching networks. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 703-712, New York, NY, USA, 2015. Association for Computing Machinery. URL: https://doi.org/10.1145/2746539.2746629.
  12. C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre. Correlation inequalities on some partially ordered sets. Communications in Mathematical Physics, 22:89-103, 1971. URL: https://doi.org/10.1007/bf01651330.
  13. Efraim Gelman and Amnon Ta-Shma. The Benes Network is q(q-1)/2n-Almost q-set-wise Independent. In Venkatesh Raman and S. P. Suresh, editors, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), volume 29 of Leibniz International Proceedings in Informatics (LIPIcs), pages 327-338, Dagstuhl, Germany, 2014. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2014.327.
  14. Mika Göös and Thomas Watson. A lower bound for sampling disjoint sets. ACM Trans. Comput. Theory, 12(3):Art. 20, 13, 2020. URL: https://doi.org/10.1145/3404858.
  15. Torben Hagerup. Fast parallel generation of random permutations. In Automata, Languages and Programming: 18th International Colloquium Madrid, Spain, July 8-12, 1991 Proceedings 18, pages 405-416. Springer, 1991. Google Scholar
  16. T. E. Harris. A lower bound for the critical probability in a certain percolation process. Proc. Cambridge Philos. Soc., 56:13-20, 1960. Google Scholar
  17. Johan Håstad. Computational limitations of small-depth circuits. MIT Press, 1987. Google Scholar
  18. Russell Impagliazzo and Moni Naor. Efficient cryptographic schemes provably as secure as subset sum. Journal of cryptology, 9(4):199-216, 1996. Google Scholar
  19. Joe Kilian. Founding crytpography on oblivious transfer. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC '88, pages 20-31, New York, NY, USA, 1988. Association for Computing Machinery. URL: https://doi.org/10.1145/62212.62215.
  20. Andreas Krebs, Nutan Limaye, Meena Mahajan, and Karteek Sreenivasaiah. Small depth proof systems. ACM Trans. Comput. Theory, 9(1):Art. 2, 26, 2016. URL: https://doi.org/10.1145/2956229.
  21. Shachar Lovett and Emanuele Viola. Bounded-depth circuits cannot sample good codes. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pages 243-251. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/CCC.2011.11.
  22. Shachar Lovett and Emanuele Viola. Bounded-depth circuits cannot sample good codes. Comput. Complexity, 21(2):245-266, 2012. URL: https://doi.org/10.1007/s00037-012-0039-3.
  23. Anup Rao. Coding for sunflowers, 2019. URL: https://doi.org/10.48550/ARXIV.1909.04774.
  24. Benjamin Rossman. The monotone complexity of k-clique on random graphs. SIAM J. Comput., 43(1):256-279, 2014. URL: https://doi.org/10.1137/110839059.
  25. R. Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, pages 77-82, New York, NY, USA, 1987. Association for Computing Machinery. URL: https://doi.org/10.1145/28395.28404.
  26. Emanuele Viola. The complexity of distributions. SIAM J. Comput., 41(1):191-218, 2012. URL: https://doi.org/10.1137/100814998.
  27. Emanuele Viola. Extractors for Turing-machine sources. In Anupam Gupta, Klaus Jansen, José D. P. Rolim, and Rocco A. Servedio, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings, volume 7408 of Lecture Notes in Computer Science, pages 663-671. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-32512-0_56.
  28. Emanuele Viola. Extractors for circuit sources. SIAM J. Comput., 43(2):655-672, 2014. URL: https://doi.org/10.1137/11085983X.
  29. Emanuele Viola. Quadratic maps are hard to sample. ACM Trans. Comput. Theory, 8(4):18:1-18:4, 2016. URL: https://doi.org/10.1145/2934308.
  30. Emanuele Viola. Sampling lower bounds: Boolean average-case and permutations. SIAM J. Comput., 49(1):119-137, 2020. URL: https://doi.org/10.1137/18M1198405.
  31. Emanuele Viola. New sampling lower bounds via the separator, 2021. Google Scholar
  32. Adam Bene Watts and Natalie Parham. Unconditional quantum advantage for sampling with shallow circuits, 2023. URL: https://arxiv.org/abs/2301.00995.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact