Document Open Access Logo

Complexity Measures on the Symmetric Group and Beyond (Extended Abstract)

Authors Neta Dafni, Yuval Filmus , Noam Lifshitz, Nathan Lindzey, Marc Vinyals

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.87.pdf
  • Filesize: 318 kB
  • 5 pages

Document Identifiers

Author Details

Neta Dafni
  • Department of Computer Science, Technion, Haifa, Israel
Yuval Filmus
  • Department of Computer Science, Technion, Haifa, Israel
Noam Lifshitz
  • Einstein Institute of Mathematics, Hebrew University of Jerusalem, Israel
Nathan Lindzey
  • Department of Computer Science, University of Colorado, Boulder, CO, USA
Marc Vinyals
  • Department of Computer Science, Technion, Haifa, Israel

Funding

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 802020-ERC-HARMONIC.

Acknowledgements

We thank Nitin Saurabh for many helpful discussions.

Cite As Get BibTex

Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, and Marc Vinyals. Complexity Measures on the Symmetric Group and Beyond (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 87:1-87:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITCS.2021.87

Abstract

We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decision tree complexity, sensitivity, block sensitivity, and a few others. We show that these complexity measures are polynomially related for the symmetric group and for many other domains.
To show that all measures but sensitivity are polynomially related, we generalize classical arguments of Nisan and others. To add sensitivity to the mix, we reduce to Huang’s sensitivity theorem using "pseudo-characters", which witness the degree of a function.
Using similar ideas, we extend the characterization of Boolean degree 1 functions on the symmetric group due to Ellis, Friedgut and Pilpel to the perfect matching scheme. As another application of our ideas, we simplify the characterization of maximum-size t-intersecting families in the symmetric group and the perfect matching scheme.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
  • Mathematics of computing → Discrete mathematics
Keywords
  • Computational Complexity Theory
  • Analysis of Boolean Functions
  • Complexity Measures
  • Extremal Combinatorics

Metrics

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

Related Versions

References

  1. Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, and David Steurer. Making the long code shorter. SIAM J. Comput., 44(5):1287-1324, 2015. URL: https://doi.org/10.1137/130929394.
  2. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theoret. Comput. Sci., 288(1):21-43, 2002. Complexity and logic (Vienna, 1998). URL: https://doi.org/10.1016/S0304-3975(01)00144-X.
  3. David Ellis. Stability for t-intersecting families of permutations. J. Combin. Theory Ser. A, 118(1):208-227, 2011. URL: https://doi.org/10.1016/j.jcta.2010.04.005.
  4. David Ellis, Ehud Friedgut, and Haran Pilpel. Intersecting families of permutations. J. Amer. Math. Soc., 24(3):649-682, 2011. URL: https://doi.org/10.1090/S0894-0347-2011-00690-5.
  5. Yuval Filmus. A comment on intersecting families of permutations. arXiv, abs/1706.10146, 2017. URL: http://arxiv.org/abs/1706.10146.
  6. Yuval Filmus and Ferdinand Ihringer. Boolean degree 1 functions on some classical association schemes. J. Combin. Theory Ser. A, 162:241-270, 2019. URL: https://doi.org/10.1016/j.jcta.2018.11.006.
  7. Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani. Optimal Sherali-Adams gaps from pairwise independence. In Approximation, randomization, and combinatorial optimization, volume 5687 of Lecture Notes in Comput. Sci., pages 125-139. Springer, Berlin, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_10.
  8. Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, and Avi Wigderson. Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions. In ITCS'16 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 59-70. ACM, New York, 2016. URL: https://doi.org/10.1145/2840728.2840738.
  9. Hao Huang. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Ann. of Math. (2), 190(3):949-955, 2019. URL: https://doi.org/10.4007/annals.2019.190.3.6.
  10. Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom sets in Grassmann graph have near-perfect expansion. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 592-601, 2018. Google Scholar
  11. Nathan Lindzey. Intersecting families of perfect matchings. ArXiv, abs/1811.06160, 2018. Google Scholar
  12. Nathan Lindzey. Matchings and representation theory. PhD thesis, University of Waterloo, 2018. Google Scholar
  13. Ryan O'Donnell and Karl Wimmer. KKL, Kruskal-Katona, and monotone nets. SIAM J. Comput., 42(6):2375-2399, 2013. URL: https://doi.org/10.1137/100787325.
  14. Alasdair Urquhart and Xudong Fu. Simplified lower bounds for propositional proofs. Notre Dame J. Formal Logic, 37(4):523-544, 1996. URL: https://doi.org/10.1305/ndjfl/1040046140.
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