EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Complexity measures on the symmetric group and beyond

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

Combinatorial Theory · 20.08.2026 · 6 (2)

DOI: 10.5070/c6.68665 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Combinatorial Theory, online erschienen am 20.08.2026. Verfasst von Neta Dafni und 4 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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. Mathematics Subject Classifications: 06E30, 94D10 Keywords: Boolean functions, complexity measures

Zitieren

APA

Dafni, N., Filmus, Y., Lifshitz, N., Lindzey, N., & Vinyals, M. (2026). Complexity measures on the symmetric group and beyond. Combinatorial Theory, 6(2). https://doi.org/10.5070/c6.68665

Vancouver

Dafni N, Filmus Y, Lifshitz N, Lindzey N, Vinyals M. Complexity measures on the symmetric group and beyond. Combinatorial Theory. 2026;6(2). doi:10.5070/c6.68665

BibTeX
@article{Dafni2026,
  author = {Dafni, Neta and Filmus, Yuval and Lifshitz, Noam and Lindzey, Nathan and Vinyals, Marc},
  title = {Complexity measures on the symmetric group and beyond},
  journal = {Combinatorial Theory},
  year = {2026},
  volume = {6},
  number = {2},
  doi = {10.5070/c6.68665}
}
Kostenlos starten →