论文标题
对称组及以后的复杂度度量
Complexity Measures on the Symmetric Group and Beyond
论文作者
论文摘要
我们将功能复杂度度量的定义扩展到对称组等领域。我们考虑的复杂性度量包括程度，近似程度，决策树的复杂性，灵敏度，障碍灵敏度以及其他一些。我们表明，这些复杂性度量与对称组和许多其他领域在多个金属上相关。 为了表明，除灵敏度以外的所有措施都与多项式相关，我们将Nisan和其他人的经典论证推广。为了增加对混合物的敏感性，我们使用“伪字符”来简化Huang的灵敏度定理，后者见证了功能的程度。 使用类似的想法，我们将布尔学位1函数的表征扩展到对称组上，因为Ellis，Friedgut和Pilpel导致了完美的匹配方案。作为我们想法的另一种应用，我们简化了对称组中最大尺寸$ t $降级家庭的表征和完美的匹配方案。
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.
