On Approximate Symmetric Polynomials and Tightness of Homogenization Results

Motivated by questions concerning the multilinear and homogeneous complexity of the elementary symmetric polynomials, we prove the following results: We first show that by making small modifications to the nonzero coefficients of the degree- K , N -variate elementary symmetric polynomial σ N,K σ N , K , one obtains a polynomial that can be computed by a monotone formula of size KO(log K) · N K O ( log K ) · N . As a corollary, we show that the result of (Raz 2013) concerning the homogenization of algebraic multilinear or monotone formulas is tight. Another corollary is that the monotone bounded rigidity of the inclusion matrix between K -subsets and $$N-K$$ N - K subsets of a universe of size N is small.