Document Open Access Logo

Diameter Versus Certificate Complexity of Boolean Functions

Authors Siddhesh Chaubal, Anna Gál

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.31.pdf
  • Filesize: 0.74 MB
  • 22 pages

Document Identifiers

Author Details

Siddhesh Chaubal
  • University of Texas at Austin, TX, USA
Anna Gál
  • University of Texas at Austin, TX, USA

Acknowledgements

We thank the anonymous referees for helpful comments on a previous version of the paper.

Cite As Get BibTex

Siddhesh Chaubal and Anna Gál. Diameter Versus Certificate Complexity of Boolean Functions. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.31

Abstract

In this paper, we introduce a measure of Boolean functions we call diameter, that captures the relationship between certificate complexity and several other measures of Boolean functions. Our measure can be viewed as a variation on alternating number, but while alternating number can be exponentially larger than certificate complexity, we show that diameter is always upper bounded by certificate complexity. We argue that estimating diameter may help to get improved bounds on certificate complexity in terms of sensitivity, and other measures.
Previous results due to Lin and Zhang [Krishnamoorthy Dinesh and Jayalal Sarma, 2018] imply that s(f) ≥ Ω(n^{1/3}) for transitive functions with constant alternating number. We improve and extend this bound and prove that s(f) ≥ √n for transitive functions with constant alternating number, as well as for transitive functions with constant diameter. {We also show that bs(f) ≥ Ω(n^{3/7}) for transitive functions under the weaker condition that the "minimum" diameter is constant.}
Furthermore, we prove that the log-rank conjecture holds for functions of the form f(x ⊕ y) for functions f with diameter bounded above by a polynomial of the logarithm of the Fourier sparsity of the function f.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
Keywords
  • Sensitivity Conjecture
  • Boolean Functions
  • Certificate Complexity
  • Block Sensitivity
  • Log-rank Conjecture
  • Alternating Number

Metrics

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

References

  1. Scott Aaronson, Shalev Ben-David, Robin Kothari, and Avishay Tal. Quantum Implications of Huang’s Sensitivity Theorem. Electronic Colloquium on Computational Complexity (ECCC), 27:66, 2020. URL: https://eccc.weizmann.ac.il/report/2020/066.
  2. Kazuyuki Amano. Minterm-transitive functions with asymptotically smallest Block Sensitivity. Inf. Process. Lett., 111(23-24):1081-1084, 2011. URL: https://doi.org/10.1016/j.ipl.2011.09.008.
  3. Kaspars Balodis. Several Separations Based on a Partial Boolean Function. arXiv e-prints, March 2021. URL: http://arxiv.org/abs/2103.05593.
  4. Richard Beigel and Anna Bernasconi. A note on the polynomial representation of boolean functions over GF(2). International Journal of Foundations of Computer Science, 10(04):535-542, 1999. URL: https://doi.org/10.1142/S012905419900037X.
  5. Shalev Ben-David, Mika Goos, Siddhartha Jain, and Robin Kothari. Unambiguous DNFs from HEX. arXiv e-prints, February 2021. URL: http://arxiv.org/abs/2102.08348.
  6. Shalev Ben-David, Pooya Hatami, and Avishay Tal. Low-Sensitivity Functions from Unambiguous Certificates. In Proceedings of Innovations in Theoretical Computer Science Conference (ITCS), pages 28:1-28:23, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.28.
  7. A. Bernasconi and B. Codenotti. Spectral analysis of boolean functions as a graph eigenvalue problem. IEEE Transactions on Computers, 48(3):345-351, 1999. Google Scholar
  8. Eric Blais, Clément L Canonne, Igor C Oliveira, Rocco A Servedio, and Li-Yang Tan. Learning circuits with few negations. arXiv preprint, 2014. URL: http://arxiv.org/abs/1410.8420.
  9. Harry Buhrman and Ronald De Wolf. Complexity Measures and Decision Tree Complexity: A Survey. Theoretical Computer Science, 288(1):21-43, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00144-X.
  10. Sourav Chakraborty. On the Sensitivity of Cyclically-Invariant Boolean functions. Discrete Mathematics & Theoretical Computer Science, 13(4):51-60, 2011. URL: http://dmtcs.episciences.org/552.
  11. J.-C Chang and H.-L Wu. The log-rank conjecture for read-k xor functions. Journal of Information Science and Engineering, 34:391-399, March 2018. Google Scholar
  12. Siddhesh Chaubal and Anna Gál. Tight bounds on sensitivity and block sensitivity of some classes of transitive functions. Electronic Colloquium on Computational Complexity (ECCC), 27:134, 2020. URL: https://eccc.weizmann.ac.il/report/2020/134/.
  13. Krishnamoorthy Dinesh and Jayalal Sarma. Alternation, Sparsity and Sensitivity: Combinatorial Bounds and Exponential Gaps. In Proceedings of the 4th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM), pages 260-273, 2018. URL: https://doi.org/10.1007/978-3-319-74180-2_22.
  14. Krishnamoorthy Dinesh and Jayalal Sarma. Sensitivity, affine transforms and quantum communication complexity. In Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings, volume 11653 of Lecture Notes in Computer Science, pages 140-152. Springer, 2019. Google Scholar
  15. Andrew Drucker. Block Sensitivity of Minterm-Transitive functions. Theor. Comput. Sci., 412(41):5796-5801, 2011. URL: https://doi.org/10.1016/j.tcs.2011.06.025.
  16. Siyao Guo, Tal Malkin, Igor C. Oliveira, and Alon Rosen. The power of negations in cryptography. In Theory of Cryptography, pages 36-65, 2015. Google Scholar
  17. Hao Huang. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Annals of Mathematics, 190(3):949-955, 2019. Google Scholar
  18. Raghav Kulkarni and Miklos Santha. Query complexity of matroids. In Paul G. Spirakis and Maria Serna, editors, Algorithms and Complexity, pages 300-311, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  19. Sophie Laplante, Reza Naserasr, and Anupa Sunny. Sensitivity Lower Bounds from Linear Dependencies. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 62:1-62:14, 2020. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.62.
  20. Chengyu Lin and Shengyu Zhang. Sensitivity Conjecture and Log-Rank Conjecture for Functions with Small Alternating Numbers. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 51:1-51:13, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.51.
  21. László Lovász and Michael Saks. Lattices, mobius functions and communications complexity. In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science, pages 81-90. IEEE Computer Society, 1988. Google Scholar
  22. A. A. Markov. On the inversion complexity of a system of functions. J. ACM, 5(4):331–334, October 1958. URL: https://doi.org/10.1145/320941.320945.
  23. Kurt Mehlhorn and Erik M. Schmidt. Las vegas is better than determinism in vlsi and distributed computing (extended abstract). In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC '82, page 330–337. Association for Computing Machinery, 1982. URL: https://doi.org/10.1145/800070.802208.
  24. Gatis Midrijanis. Exact quantum query complexity for total boolean functions. arXiv preprint, 2004. URL: http://arxiv.org/abs/quant-ph/0403168.
  25. Ashley Montanaro and Tobias Osborne. On the communication complexity of XOR functions. CoRR, abs/0909.3392, 2009. URL: http://arxiv.org/abs/0909.3392.
  26. Hiroki Morizumi. Limiting negations in formulas. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I, ICALP '09, page 701–712. Springer-Verlag, 2009. URL: https://doi.org/10.1007/978-3-642-02927-1_58.
  27. Hiroki Morizumi. Limiting negations in non-deterministic circuits. Theoretical Computer Science, 410(38):3988-3994, 2009. URL: https://doi.org/10.1016/j.tcs.2009.05.018.
  28. Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4(4):301-313, December 1994. URL: https://doi.org/10.1007/BF01263419.
  29. Noam Nisan and Avi Wigderson. On rank vs. communication complexity. Comb., 15(4):557-565, 1995. URL: https://doi.org/10.1007/BF01192527.
  30. Ryan O'Donnell. Analysis of Boolean functions. Cambridge University Press, 2014. Google Scholar
  31. Miklos Santha and Christopher Wilson. Limiting negations in constant depth circuits. SIAM Journal on Computing, 22(2):294-302, 1993. URL: https://doi.org/10.1137/0222022.
  32. Xiaoming Sun. Block Sensitivity of Weakly Symmetric Functions. In Proceedings of the Third International Conference on Theory and Applications of Models of Computation (TAMC), pages 339-344, 2006. URL: https://doi.org/10.1007/11750321_32.
  33. Xiaoming Sun. An improved lower bound on the Sensitivity Complexity of Graph Properties. Theor. Comput. Sci., 412(29):3524-3529, 2011. URL: https://doi.org/10.1016/j.tcs.2011.02.042.
  34. Shao Chin Sung and Keisuke Tanaka. Limiting negations in bounded-depth circuits: An extension of markov’s theorem. In Algorithms and Computation, pages 108-116. Springer, 2003. Google Scholar
  35. H. Y. Tsang, C. H. Wong, N. Xie, and S. Zhang. Fourier sparsity, spectral norm, and the log-rank conjecture. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 658-667, 2013. Google Scholar
  36. Hing Yin Tsang. On boolean functions with low sensitivity. Manuscript, 2014. URL: http://theorycenter.cs.uchicago.edu/REU/2014/final-papers/tsang.pdf.
  37. Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang. Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 658-667, 2013. URL: https://doi.org/10.1109/FOCS.2013.76.
  38. Gyorgy Turan. The Critical Complexity of Graph Properties. Information Processing Letters, 18(3):151-153, 1984. URL: https://doi.org/10.1016/0020-0190(84)90019-X.
  39. Zhiqiang Zhang and Yaoyun Shi. Communication complexities of symmetric xor functions. Quantum Info. Comput., 9(3):255–263, 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact