Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton
Polynomials that Sign Represent Parity and Descartes Rule of Signs

Abstract: We study the sparsity of real polynomials that sign represent parity on n variables taking values in a finite set of integers A. Although the degree of such polynomials has been well studied, the same is not true for the sparsity. One obstacle in the study of sparsity is that the bounds can vary very much depending on the choice of A.
A classical result from algebra known as Descartes Rule of Signs states that the number of positive real roots (counted with multiplicity) of a univariate polynomial P is bounded by the number of variations in the sign of its coefficients written in order, and in particular, by one less that the sparsity of P. Our techniques overcome the difficulty above and allow us to prove bounds on the sparsity of polynomials, for many choices of A, and different bases for polynomials for which Descartes Rule holds.
For strong representations, using Descartes Rule of Signs we reprove the result of Minsky and Papert that representing parity over A = {0,1}, in n variables requires sparsity 2ⁿ . We can show exact bounds on the sparsity of such polynomials for any A of size 2. This can be extended to show that representing parity over A = {0, ... , m-1} in n variables requires sparsity mⁿ  when the degree in each variable is at most m-1.
We show that weakly sign representing parity over A = {0, ... ,m-1} when the degree in each variable is restricted to m-1 requires sparsity (m-1)ⁿ. These results show that  low degree representations must have high sparsity. We show that a tradeoff exists between sparsity and degree by constructing a sign representation for parity that has high degree, but sparsity only ^n+m-1C_n for any set A of size m. In the case A= {1,2}this is an exponential difference in sparsity. We  also show a lower bound of n(m-1) +1 on the sparsity of polynomials of arbitrary degree sign representing parity over {1, ... ,m}.

We can show that for depth-two AND-OR-NOT circuits with a threshold gate at the top, the minimum circuit size for a function f equals the minimum sparsity of a polynomial sign representing f over a certain  generating set for polynomials . We use this to give a proof that  circuits of this type need size (3/2)ⁿ  to compute parity. We also show a  lower bound of 2ⁿ for the size of  such a circuit which computes the inner product function over {0,1}ⁿ  x {0,1}ⁿ.