Polynomials that sign represent parity and Descartes' rule of signs

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

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

Publication date 17 June 2009

Published in Computational Complexity (Search for Journal in Brave)

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)

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$.

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

Cited in

(3)

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

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)