Computer Science

The correlation between parity and quadratic polynomials mod 3

Document Type

Article

Abstract

We prove exponentially small upper bounds on the correlation between parity and quadratic polynomials mod3. One corollary of this is that in order to compute parity, circuits consisting of a threshold gate at the top, mod3 gates in the middle, and AND gates of fan-in two at the inputs must be of size 2 Ω(n). This is the first result of this type for general mod3 subcircuits with ANDs of fan-in greater than 1. This yields an exponential improvement over a long-standing result of Smolensky, answering a question recently posed by Alon and Beigel. The proof uses a novel inductive estimate of the relevant exponential sums introduced by Cai, Green and Thierauf. The exponential sum and correlation bounds presented here are tight. © 2004 Elsevier Inc. All rights reserved.

Publication Title

Journal of Computer and System Sciences

Publication Date

2004

Volume

69

Issue

1

First Page

28

Last Page

44

ISSN

0022-0000

DOI

10.1016/j.jcss.2004.01.003

Keywords

circuit complexity, computational complexity, lower bounds

APA Citation

Green, F. (2004). The correlation between parity and quadratic polynomials mod 3. Journal of Computer and System Sciences, 69(1), 28-44.

Link to Full Text

Share

COinS