Polynomials that Sign Represent Parity and Descartes' Rule of Signs

Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. LiptonComputational Complexity Conference 2004 · OpenReview

TL;DR

This paper investigates the "sparsity" (number of terms) of polynomials used to represent the parity function. By leveraging Descartes' Rule of Signs, the authors establish new lower bounds on sparsity, revealing trade-offs between sparsity and polynomial degree, and providing insights into circuit complexity.

What Problem Does This Paper Address?

In computer science, particularly in areas like circuit complexity and computational learning theory, researchers often represent functions using polynomials. Two key properties of these polynomials are their degree (the highest power of any variable) and their sparsity (the number of distinct terms or monomials with non-zero coefficients). While the minimum degree required to represent a function is relatively well-understood, the minimum sparsity is often much harder to determine and can vary significantly. This paper focuses on the parity function, a fundamental building block in computation, and aims to understand the minimum sparsity of polynomials that can "sign represent" it. Sign representation is a weaker condition than exact representation: it only requires the polynomial's sign to match the function's output (0 or 1). The challenge is to find these sparsity bounds for polynomials where variables can take values from arbitrary finite sets, not just the usual {0, 1} or {-1, +1}.

Methods

The core technical tool employed in this paper is Descartes' Rule of Signs. This classical algebraic result provides an upper bound on the number of positive real roots of a univariate polynomial based on the number of sign changes in its coefficients. The authors cleverly adapt this rule to derive bounds on the sparsity of polynomials.

Key techniques include:

  • Self-reducibility of Parity: The parity function has a recursive structure that allows polynomials representing it to be broken down into smaller instances. This is used extensively to relate the sparsity of a polynomial in $n$ variables to the sparsity of polynomials in $n-1$ variables.
  • Symmetrization and Degree Reduction: For symmetric functions, it's often possible to assume the representing polynomial is also symmetric, and to reduce the degree of each variable. While useful for degree, this doesn't directly simplify sparsity.
  • Vandermonde Matrices and their Inverses: The paper utilizes properties of Vandermonde matrices and their inverses to analyze the signs of coefficients and relationships between different polynomial representations.
  • Constructive Proofs: For upper bounds, the authors construct specific polynomials that achieve certain sparsity-degree trade-offs.

Datasets

Not discussed in the paper. The paper deals with theoretical functions and polynomial representations, not empirical datasets.

Key Insights and Ideas

  • Descartes' Rule of Signs as a Sparsity Tool: The paper demonstrates a powerful, albeit elementary, application of Descartes' Rule of Signs to derive non-trivial lower bounds on polynomial sparsity, a problem that has eluded more complex methods.
  • Sparsity vs. Degree Trade-off: A significant finding is that one can achieve lower sparsity by allowing higher degrees. This contrasts with the degree-bound perspective and highlights a fundamental trade-off in polynomial representations.
  • Generalizing Beyond Boolean Inputs: The work extends the analysis of polynomial representations from the standard {0,1} or {-1,+1} inputs to arbitrary finite sets of integers, showing that the choice of input set can significantly impact sparsity requirements.
  • Connection to Circuit Complexity: The paper establishes a direct link between the sparsity of polynomials representing parity and the size of certain restricted circuits (Threshold of ANDs circuits). This allows for proving circuit lower bounds by proving polynomial sparsity bounds.

Key Results

  • Parity over {0, ..., m-1}$^n$: A polynomial representing parity with degree at most $m-1$ in each variable requires sparsity at least $m^n$.
  • Weak Representations: For weak representations of parity over {0, ..., m-1}$^n$ with degree at most $m-1$, a lower bound of $(m-1)^n$ on sparsity is shown.
  • Degree-Sparsity Trade-off: A polynomial representing parity over {1,2}$^n$ is constructed with degree $n^2$ and sparsity $n+1$, demonstrating that lower sparsity is achievable with higher degree compared to multilinear polynomials.
  • Exact Bounds for Two-Element Sets: Exact bounds on sparsity are proven for parity representation over any two-element subset $A$.
  • Circuit Lower Bounds:
    • Threshold of ANDs circuits for parity require size at least $(3/2)^n$, improving on previous bounds.
  • THR $\circ$ AND circuits for the inner product function over {0,1}$^n \times$ {0,1}$^n$ require size at least $2^n$.

Limitations and Future Work

  • Gap for Large Sets: For arbitrary sets $A$ of size $m > 2$, the paper establishes lower bounds on sparsity but is unable to close the gap between these lower bounds and the upper bounds derived from constructions. This suggests that further work is needed to fully characterize sparsity for larger input sets.
  • Generalization of Descartes' Rule: The paper notes that a proper generalization of Descartes' Rule of Signs to multivariate polynomials remains an open problem in real algebraic geometry. Progress in this area could lead to tighter bounds.
  • Exploring Other Functions: While parity is a key focus, the methods might be applicable to other related functions, and exploring these connections could be a fruitful direction.
  • Circuit Complexity: The paper connects sparsity to circuit size for specific circuit models. Extending these connections to other circuit classes or computational models could be valuable.

Summary updated

Abstract

A real polynomial P(X 1, ... , X n ) sign represents f : A n → {0, 1} if for every (a 1, ... , a n ) ∈ A n , the sign of P(a 1, ... ,a n ) equals $$(-1)^{f(a_{1}, \ldots ,a_{n})}$$ . Such sign representations are well-studied in computer science and have applications to computational complexity and computational learning theory. The work in this area aims to determine the minimum degree and sparsity possible for a polynomial that sign represents a function f. While the degree of such polynomials is relatively well-understood, far less is known about their sparsity. Known bounds apply only to the cases where A = {0, 1} or A = {−1, +1}.In this work, we present a systematic study of tradeoffs between degree and sparsity of sign representations through the lens of the parity function. We attempt to prove bounds that hold for any choice of set A. We show that sign representing parity over {0,... , m − 1} n with the degree in each variable at most m − 1 requires sparsity at least m n . We show that a tradeoff exists between sparsity and degree, by exhibiting a sign representation that has higher degree but lower sparsity. We show a lower bound of n(m − 2) + 1 on the sparsity of polynomials of any degree representing parity over {0,... ,m − 1} n . We prove exact bounds on the sparsity of such polynomials for any two element subset A. The main tool used is Descartes’ Rule of Signs, a classical result in algebra, relating the sparsity of a polynomial to its number of real roots. As an application, we use bounds on sparsity to derive circuit lower bounds for depth-two AND-OR-NOT circuits with a Threshold Gate at the top.
BibTeX
@inproceedings{basu2004polynomials,
  author = {Saugata Basu and Nayantara Bhatnagar and Parikshit Gopalan and Richard J. Lipton},
  title = {{Polynomials that Sign Represent Parity and Descartes' Rule of Signs}},
  booktitle = {Computational Complexity Conference},
  year = {2004},
  url = {https://openreview.net/forum?id=2SIxXQ2cMJ},
}
Figure