Complexity Measures on the Symmetric Group and Beyond

Neta Dafni, Yuval Filmus, Noam Lifshitz +2

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, decisi…