  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.
