Polynomials that sign represent parity and Descartes' rule of signs

DOI10.1007/S00037-008-0244-2zbMATH Open1188.68150arXivmath/0702773OpenAlexW2145490171MaRDI QIDQ1024658FDOQ1024658

Nayantara Bhatnagar, Richard J. Lipton, Parikshit Gopalan, Saugata Basu

Publication date: 17 June 2009

Published in: Computational Complexity (Search for Journal in Brave)

Abstract: A real polynomial $P(X_1,\mathrm{...},X_n)$ sign represents $f:A^{n}o0,1$ if for every $(a_1,\mathrm{...},a_n)in{A}^n$, the sign of $P(a_1,\mathrm{...},a_n)$ equals $(-1{)}^{f(a_1,\mathrm{...},a_n)}$. Such sign representations are well-studied in computer science and have applications to computational complexity and computational learning theory. 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,\mathrm{...},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,\mathrm{...},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. We use this to give a simple proof that such circuits need size $1.5^n$ to compute parity, which improves the previous bound of ${4/3}^{n/2}$ due to Goldmann (1997). We show a tight lower bound of $2^n$ for the inner product function over ${0,1}^{n}imes{0,1}^n$.

Full work available at URL: https://arxiv.org/abs/math/0702773

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (3)

• Nearest neighbor representations of Boolean functions
• Polynomial threshold functions and Boolean threshold circuits
• A converse rule of signs for polynomials

   Recommendations

• New degree bounds for polynomial threshold functions 👍 👎
• Optimal Descartes' rule of signs for systems supported on circuits 👍 👎
• Degree-uniform lower bound on the weights of polynomials with given sign function 👍 👎
• Descartes’ Rule of Signs for Polynomial Systems Supported on Circuits 👍 👎
• Descartes' Rule of Signs Revisited 👍 👎

This page was built for publication: Polynomials that sign represent parity and Descartes' rule of signs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024658)