Improved Monotonicity Testers via Hypercube Embeddings

Authors Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.25.pdf
  • Filesize: 0.79 MB
  • 24 pages

Document Identifiers

Author Details

Mark Braverman
  • Department of Computer Science, Princeton University, NJ, USA
Subhash Khot
  • Courant institute of Mathematical Sciences, New York University, NY, USA
Guy Kindler
  • Engineering and Computer Science Department, The Hebrew University, Jerusalem, USA
Dor Minzer
  • Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA

Cite AsGet BibTex

Mark Braverman, Subhash Khot, Guy Kindler, and Dor Minzer. Improved Monotonicity Testers via Hypercube Embeddings. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 25:1-25:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.25

Abstract

We show improved monotonicity testers for the Boolean hypercube under the p-biased measure, as well as over the hypergrid [m]ⁿ. Our results are: 1) For any p ∈ (0,1), for the p-biased hypercube we show a non-adaptive tester that makes Õ(√n/ε²) queries, accepts monotone functions with probability 1 and rejects functions that are ε-far from monotone with probability at least 2/3. 2) For all m ∈ ℕ, we show an Õ(√nm³/ε²) query monotonicity tester over [m]ⁿ. We also establish corresponding directed isoperimetric inequalities in these domains, analogous to the isoperimetric inequality in [Subhash Khot et al., 2018]. Previously, the best known tester due to Black, Chakrabarty and Seshadhri [Hadley Black et al., 2018] had Ω(n^{5/6}) query complexity. Our results are optimal up to poly-logarithmic factors and the dependency on m. Our proof uses a notion of monotone embeddings of measures into the Boolean hypercube that can be used to reduce the problem of monotonicity testing over an arbitrary product domains to the Boolean cube. The embedding maps a function over a product domain of dimension n into a function over a Boolean cube of a larger dimension n', while preserving its distance from being monotone; an embedding is considered efficient if n' is not much larger than n, and we show how to construct efficient embeddings in the above mentioned settings.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
  • Mathematics of computing → Combinatorics
Keywords
  • Property Testing
  • Monotonicity Testing
  • Isoperimetric Inequalities

Metrics

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

References

  1. A matching for [4]ⁿ. https://www.cs.huji.ac.il/w~gkindler/matchings/index.html. Accessed: 2022-08-06.
  2. Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri. A o(d) ⋅ polylog n monotonicity tester for boolean functions over the hypergrid [n]^d. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2133-2151, 2018. URL: https://doi.org/10.1137/1.9781611975031.139.
  3. Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri. Domain reduction for monotonicity testing: A o(d) tester for boolean functions in d-dimensions. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1975-1994, 2020. URL: https://doi.org/10.1137/1.9781611975994.122.
  4. Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri. Directed isoperimetric theorems for boolean functions on the hypergrid and an Õ(n√d) monotonicity tester, 2022. URL: https://doi.org/10.48550/arXiv.2211.05281.
  5. Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova. Isoperimetric inequalities for real-valued functions with applications to monotonicity testing. arXiv preprint, 2020. URL: http://arxiv.org/abs/2011.09441.
  6. Béla Bollobás and Arthur G Thomason. Threshold functions. Combinatorica, 7(1):35-38, 1987. Google Scholar
  7. Deeparnab Chakrabarty and C. Seshadhri. An optimal lower bound for monotonicity testing over hypergrids. Theory Comput., 10:453-464, 2014. URL: https://doi.org/10.4086/toc.2014.v010a017.
  8. Deeparnab Chakrabarty and C. Seshadhri. An o(n) monotonicity tester for boolean functions over the hypercube. SIAM J. Comput., 45(2):461-472, 2016. URL: https://doi.org/10.1137/13092770X.
  9. Xi Chen, Rocco A. Servedio, and Li-Yang Tan. New algorithms and lower bounds for monotonicity testing. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 286-295, 2014. URL: https://doi.org/10.1109/FOCS.2014.38.
  10. Xi Chen, Erik Waingarten, and Jinyu Xie. Beyond talagrand functions: new lower bounds for testing monotonicity and unateness. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 523-536, 2017. URL: https://doi.org/10.1145/3055399.3055461.
  11. Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. Improved testing algorithms for monotonicity. In Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques, pages 97-108. Springer, 1999. Google Scholar
  12. Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky. Monotonicity testing over general poset domains. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 474-483, 2002. URL: https://doi.org/10.1145/509907.509977.
  13. Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky. Testing monotonicity. Comb., 20(3):301-337, 2000. URL: https://doi.org/10.1007/s004930070011.
  14. Gyula Katona. A theorem of finite sets. In Classic Papers in Combinatorics, pages 381-401. Springer, 2009. Google Scholar
  15. Subhash Khot, Dor Minzer, and Muli Safra. On monotonicity testing and boolean isoperimetric-type theorems. SIAM J. Comput., 47(6):2238-2276, 2018. URL: https://doi.org/10.1137/16M1065872.
  16. Joseph B Kruskal. The number of simplices in a complex. Mathematical optimization techniques, 10:251-278, 1963. Google Scholar
  17. G. A. Margulis. Probabilistic characteristics of graphs with large connectivity. Problemy Peredači Informacii, 10(2):101-108, 1974. Google Scholar
  18. Ryan O'Donnell and Karl Wimmer. KKL, Kruskal-Katona, and monotone nets. SIAM Journal on Computing, 42(6):2375-2399, 2013. Google Scholar
  19. M. Talagrand. Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem. Geom. Funct. Anal., 3(3):295-314, 1993. URL: https://doi.org/10.1007/BF01895691.
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