Computing the Elementary Symmetric Polynomials in Positive Characteristics
Ian Orzel
原文摘要
We first extend the results of Chatterjee, Kumar, Shi, Volk (Computational Complexity 2022) by showing that the degree-$d$ elementary symmetric polynomials in $n$ variables have arithmetic formula lower bounds of $Ω(d(n-d))$ over fields of positive characteristic. This is done by characterizing the dimension of the singular locus of the elementary symmetric polynomials in positive characteristic fields (parts of the characterization only hold over infinite fields). Then, we show that the results of the universality of border fan-in-two $ΣΠΣ$-circuits from Kumar (ACM Trans. Comput. Theory 2020) over zero-characteristic fields do not extend to fields of positive characteristic. This is done through studying linear projections of the elementary symmetric polynomial as studied by Shpilka (Journal of Computer and System Sciences 2002).
cs.CC