Computer Science

Uniqueness of Optimal Mod 3 Circuits for Parity

Document Type

Conference Paper

Abstract

In this paper, we prove that the quadratic polynomials modulo 3 with the largest correlation with parity are unique up to permutation of variables and constant factors. As a consequence of our result, we completely characterize the smallest MAJ◦ MOD3 ◦ AND2 circuits that compute parity, where a MAJ ◦ MOD3 ◦ AND2 circuit is one that has a majority gate as output, a middle layer of MOD3 gates and a bottom layer of AND gates of fan-in 2. We also prove that the sub-optimal circuits exhibit a stepped behavior: any sub-optimal circuits of this class that compute parity must have size at least a factor of√23 times the optimal size. This verifies, for the special case of m = 3, two conjectures made in [5] for general MAJ ◦ MODm ◦ AND2 circuits for any odd m. The correlation and circuit bounds are obtained by studying the associated exponential sums, based on some of the techniques developed in [7].

Publication Title

Dagstuhl Seminar Proceedings

Publication Date

2008

Volume

7411

ISSN

1862-4405

DOI

10.4230/DagSemProc.07411.7

Keywords

circuit complexity correlations exponential sums

APA Citation

Green, F., & Roy, A. (2008). Uniqueness of optimal mod 3 circuits for parity. In Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.

Link to Full Text

Share

COinS