We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
On the Correlation Between Parity and Modular Polynomials.
- Authors
Gál, Anna; Trifonov, Vladimir
- Abstract
We consider the problem of bounding the correlation between parity and modular polynomials over ℤ, for arbitrary odd integer q≥3. We prove exponentially small upper bounds for classes of polynomials with certain linear algebraic properties. As a corollary, we obtain exponential lower bounds on the size necessary to compute parity by depth-3 circuits with a MAJORITY gate at the top, MOD gates at the middle level and AND gates at the input level, when the polynomials corresponding to the depth-2 MOD○ AND subcircuits satisfy our conditions. Our methods also yield lower bounds for depth-3 MAJ○ MOD○ MOD circuits (under certain restrictions) for computing parity. Our technique is based on a new general representation of the correlation using exponential sums, that allows to take advantage of the linear algebraic structure of the corresponding polynomials. Our results include Goldman's result (Goldmann in Inf. Process. Lett. 53:321-327, ) on the correlation between parity and degree one polynomials as a special case. We also present a general expression for representing correlation, that can be used to yield our results as well as to derive the bounds of Cai, Green, and Thierauf (Math. Syst. Theory 29:245-258, ) for symmetric polynomials, using ideas of the Cai et al. (Math. Syst. Theory 29:245-258, ) proof. The classes of polynomials for which we obtain exponentially small upper bounds include polynomials of very large degree and with a very large number of terms, that previous techniques did not apply to.
- Subjects
STATISTICAL correlation; POLYNOMIALS; MODULES (Algebra); LINEAR algebra; INTEGRATED circuits; COMPUTATIONAL complexity
- Publication
Theory of Computing Systems, 2012, Vol 50, Issue 3, p516
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-011-9332-9