License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.87
URN: urn:nbn:de:0030-drops-136267
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13626/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
LIPIcs-ITCS-2021-87.pdf (0.3 MB)

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.

BibTeX - Entry

@InProceedings{dafni_et_al:LIPIcs.ITCS.2021.87,
  author =	{Neta Dafni and Yuval Filmus and Noam Lifshitz and Nathan Lindzey and Marc Vinyals},
  title =	{{Complexity Measures on the Symmetric Group and Beyond}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{87:1--87:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{James R. Lee},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13626},
  URN =		{urn:nbn:de:0030-drops-136267},
  doi =		{10.4230/LIPIcs.ITCS.2021.87},
  annote =	{Keywords: Computational Complexity Theory, Analysis of Boolean Functions, Complexity Measures, Extremal Combinatorics}
}

Keywords: Computational Complexity Theory, Analysis of Boolean Functions, Complexity Measures, Extremal Combinatorics
Collection: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Issue Date: 2021
Date of publication: 04.02.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI