Complexity measures on symmetric group and beyond
summary
Defines an abstract simplicial complex framework that extends degree, decision tree complexity and sensitivity from the hypercube to domains like the symmetric group and proves they are polynomially related there. Degree is spectral via S_n irreps (Fourier degree = n − λ1) and also as minimal polynomial degree. Proof uses representation theory, lambda polytabloids as pseudo-characters, reduction to hypercubes and Erdos–Ko–Rado facts to show the domain is alpha-witnessing with alpha = 1/2, yielding a Huang-style bound s(f) = Ω(√(deg f)).
AI-written summary · about