|
Published Articles >> Table of Contents >> Abstract
19th Annual IEEE Conference on Computational Complexity (CCC'04)
pp. 223-235
Polynomials That Sign Represent Parity and Descartes Rule of Signs
Saugata Basu, Georgia Tech
Nayantara Bhatnagar, Georgia Tech
Parikshit Gopalan, Georgia Tech
Richard J. Lipton, Georgia Tech
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313846
Send link to a friend
| Abstract |
|
We study the sparsity of real polynomials that sign represent parity on n variables, each of which takes values from some finite subset A of integers. While the degree of such polynomials has been well studied [15, 1], relatively little is known about their sparsity. We study this problem using Descartes Rule of Signs, a classical result in algebra, relating the sparsity of a polynomial to its number of real roots. We show that sign representing parity over \{ 0,1 \ldots ,m - 1\} ^n with the degree in each variable at most m - 1 requires sparsity at least m^n We show a bound of (m - 1)^n for weak representations.We show that a tradeoff exists between sparsity and degree, by constructing a sign representation that has higher degree but lower sparsity. In some cases, the difference in sparsities is exponential. We show a lower bound of n(m - 2) + 1on the sparsity of polynomials of any degree representing parity over \{ 0,1, \cdots ,m - 1\} ^n. We prove exact bounds on the sparsity of such polynomials for any two element subset A We 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 basis.We use this to give a simple proof that such circuits need size (3/2n) to compute parity, which improves on previous bounds [8]. We also show a tight lower bound of 2^n for the inner product function over \{ 0,1\} ^n \times \{ 0,1\} ^n. The main technical tool used is Descartes rule of signs. Our bounds hold for various bases where Descartes sign rule is valid.
|
 Additional Information
|
Citation:
Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton,
"Polynomials That Sign Represent Parity and Descartes Rule of Signs,"
ccc,
pp. 223-235,
19th Annual IEEE Conference on Computational Complexity (CCC'04),
2004
|
|
