Document Open Access Logo

Separations Between Combinatorial Measures for Transitive Functions

Authors Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.36.pdf
  • Filesize: 0.83 MB
  • 20 pages

Document Identifiers

Author Details

Sourav Chakraborty
  • Indian Statistical Institute, Kolkata, India
Chandrima Kayal
  • Indian Statistical Institute, Kolkata, India
Manaswi Paraashar
  • Aarhus University, Denmark

Cite As Get BibTex

Sourav Chakraborty, Chandrima Kayal, and Manaswi Paraashar. Separations Between Combinatorial Measures for Transitive Functions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.36

Abstract

The role of symmetry in Boolean functions f:{0, 1}ⁿ → {0, 1} has been extensively studied in complexity theory. For example, symmetric functions, that is, functions that are invariant under the action of 𝖲_n, is an important class of functions in the study of Boolean functions. A function f:{0, 1}ⁿ → {0, 1} is called transitive (or weakly-symmetric) if there exists a transitive group 𝖦 of 𝖲_n such that f is invariant under the action of 𝖦. In other words, the value of the function remains unchanged even after the input bits of f are moved around according to some permutation σ ∈ 𝖦. Understanding various complexity measures of transitive functions has been a rich area of research for the past few decades.
This work studies transitive functions in light of several combinatorial measures. The question that we try to address in this paper is what are the maximum separations between various pairs of combinatorial measures for transitive functions. Such study for general Boolean functions has been going on for many years. Aaronson et al. (STOC, 2021) have nicely compiled the current best-known results for general Boolean functions. But before this paper, no such systematic study had been done on the case of transitive functions. 
Separations between a pair of combinatorial measures are shown by constructing interesting functions that demonstrate the separation. Over the past three decades, various interesting classes of functions have been designed for this purpose. In this context, one of the celebrated classes of functions is the "pointer functions". Ambainis et al. (JACM, 2017) constructed several functions, which are modifications of the pointer function in Göös et al. (SICOMP, 2018 / FOCS, 2015), to demonstrate the separation between various pairs of measures. In the last few years, pointer functions have been used to show separation between various other pairs of measures (Eg: Mukhopadhyay et al. (FSTTCS, 2015), Ben-David et al. (ITCS, 2017), Göös et al. (ToCT, 2018 / ICALP, 2017)). 
However, the pointer functions themselves are not transitive. Based on the various kinds of pointer functions, we construct new transitive functions, which we use to demonstrate similar separations between various pairs of combinatorial measures as demonstrated by the original pointer functions. Our construction of transitive functions depends crucially on the construction of particular classes of transitive groups whose actions, though involved, help to preserve certain structural features of the input strings. The transitive groups we construct may be of independent interest in other areas of mathematics and theoretical computer science. 
We summarize the current knowledge of relations between various combinatorial measures of transitive functions in a table similar to the table compiled by Aaronson et al. (STOC, 2021) for general functions.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Transitive functions
  • Combinatorial complexity of Boolean functions

Metrics

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

Related Versions

References

  1. Scott Aaronson, Shalev Ben-David, and Robin Kothari. Separations in query complexity using cheat sheets. In STOC, pages 863-876, 2016. URL: https://doi.org/10.1145/2897518.2897644.
  2. Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal. Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem. In STOC, pages 1330-1342, 2021. URL: https://doi.org/10.1145/3406325.3451047.
  3. Andris Ambainis. Superlinear advantage for exact quantum algorithms. SIAM Journal on Computing, pages 617-631, 2016. URL: https://doi.org/10.1137/130939043.
  4. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. Separations in query complexity based on pointer functions. Journal of the ACM, 64(5):32:1-32:24, 2017. URL: https://doi.org/10.1145/3106234.
  5. Kaspars Balodis. Several separations based on a partial Boolean function. CoRR, 2021. URL: http://arxiv.org/abs/2103.05593.
  6. Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, and Robin Kothari. Unambiguous DNFs and Alon-Saks-Seymour. In FOCS, pages 116-124, 2022. URL: https://doi.org/10.1109/FOCS52979.2021.00020.
  7. Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, and Daochen Wang. Symmetries, graph properties, and quantum speedups. In FOCS, pages 649-660, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00066.
  8. Shalev Ben-David, Mika Göös, Siddhartha Jain, and Robin Kothari. Unambiguous DNFs from Hex. Electronic Colloquium on Computational Complexity, 28:16, 2021. Google Scholar
  9. Shalev Ben-David, Pooya Hatami, and Avishay Tal. Low-sensitivity functions from unambiguous certificates. In ITCS, volume 67, pages 28:1-28:23, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.28.
  10. Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM journal on Computing, 26(5):1510-1523, 1997. URL: https://doi.org/10.1137/S0097539796300933.
  11. Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53-74, 2002. Google Scholar
  12. 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.
  13. Mark Bun and Justin Thaler. A nearly optimal lower bound on the approximate degree of AC^0. SIAM Journal on Computing, 49(4), 2020. URL: https://doi.org/10.1137/17M1161737.
  14. Sourav Chakraborty. On the sensitivity of cyclically-invariant Boolean functions. Discrete Mathematics and Theoretical Computer Science, 13(4):51-60, 2011. URL: https://doi.org/10.46298/dmtcs.552.
  15. Sourav Chakraborty, Chandrima Kayal, and Manaswi Paraashar. Separations between combinatorial measures for transitive functions. ArXiv, 2021. URL: http://arxiv.org/abs/2103.12355.
  16. Andrew Drucker. Block sensitivity of minterm-transitive functions. Theoretical Computer Science, 412(41):5796-5801, 2011. URL: https://doi.org/10.1016/j.tcs.2011.06.025.
  17. Yihan Gao, Jieming Mao, Xiaoming Sun, and Song Zuo. On the sensitivity complexity of bipartite graph properties. Theoretical Computer Science, 468:83-91, 2013. URL: https://doi.org/10.1016/j.tcs.2012.11.006.
  18. Justin Gilmer, Michael E. Saks, and Srikanth Srinivasan. Composition limits and separating examples for some Boolean function complexity measures. Combinatorica, 36(3):265-311, 2016. URL: https://doi.org/10.1007/s00493-014-3189-x.
  19. Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized communication versus partition number. ACM Transactions on Computation Theory, 10(1):4:1-4:20, 2018. URL: https://doi.org/10.1145/3170711.
  20. Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. SIAM Journal on Computing, 47(6):2435-2450, 2018. URL: https://doi.org/10.1137/16M1059369.
  21. Hao Huang. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Annals of Mathematics, 190(3):949-955, 2019. URL: https://doi.org/10.4007/annals.2019.190.3.6.
  22. Troy Lee and Jérémie Roland. A strong direct product theorem for quantum query complexity. Computational Complexity, 22(2):429-462, 2013. URL: https://doi.org/10.1109/CCC.2012.17.
  23. Qian Li and Xiaoming Sun. On the sensitivity complexity of k-uniform hypergraph properties. In STACS, volume 66, pages 51:1-51:12, 2017. URL: https://doi.org/10.4230/LIPIcs.STACS.2017.51.
  24. Sagnik Mukhopadhyay and Swagato Sanyal. Towards better separation between deterministic and randomized query complexity. In FSTTCS, volume 45, pages 206-220, 2015. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2015.206.
  25. Noam Nisan and Avi Wigderson. On rank vs. communication complexity. Combinatorica, 15(4):557-565, 1995. URL: https://doi.org/10.1007/BF01192527.
  26. David Rubinstein. Sensitivity vs. block sensitivity of Boolean functions. Combinatorica, 15(2):297-299, 1995. URL: https://doi.org/10.1007/BF01200762.
  27. Marc Snir. Lower bounds on probabilistic linear decision trees. Theoretical Computer Science, 38:69-82, 1985. URL: https://doi.org/10.1016/0304-3975(85)90210-5.
  28. Xiaoming Sun. Block sensitivity of weakly symmetric functions. Theoretical Computer Science, 384(1):87-91, 2007. URL: https://doi.org/10.1016/j.tcs.2007.05.020.
  29. Xiaoming Sun. An improved lower bound on the sensitivity complexity of graph properties. Theoretical Computer Science, 412(29):3524-3529, 2011. URL: https://doi.org/10.1016/j.tcs.2011.02.042.
  30. Xiaoming Sun, Andrew Chi-Chih Yao, and Shengyu Zhang. Graph properties and circular functions: How low can quantum query complexity go? In CCC, pages 286-293, 2004. URL: https://doi.org/10.1109/CCC.2004.1313851.
  31. György Turán. 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.
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