Green, Frederic ;
Roy, Amitabha
Uniqueness of Optimal Mod 3 Circuits for Parity
Abstract
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~$circ mbox{MOD}_3 circ {
m AND}_2$ circuits that compute parity, where a
MAJ~$circ mbox{MOD}_3 circ {
m AND}_2$ circuit is one that has a
majority gate as output, a middle layer of MOD$_3$ gates and a
bottom layer of AND gates of fanin $2$. We
also prove that the suboptimal circuits exhibit a stepped behavior:
any suboptimal circuits of this class that compute parity
must have size at least a factor of $frac{2}{sqrt{3}}$ times the
optimal size. This verifies, for the special case of $m=3$,
two conjectures made
by Due~{n}ez, Miller, Roy and Straubing (Journal of Number Theory, 2006) for general MAJ~$circ mathrm{MOD}_m circ
{
m AND}_2$ 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
by Green (JCSS, 2004). We regard this as a step towards
obtaining tighter bounds both for the $m
ot = 3$ quadratic
case as well as for
higher degrees.
BibTeX  Entry
@InProceedings{green_et_al:DagSemProc.07411.7,
author = {Green, Frederic and Roy, Amitabha},
title = {{Uniqueness of Optimal Mod 3 Circuits for Parity}},
booktitle = {Algebraic Methods in Computational Complexity},
pages = {115},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {18624405},
year = {2008},
volume = {7411},
editor = {Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2008/1305},
URN = {urn:nbn:de:0030drops13059},
doi = {10.4230/DagSemProc.07411.7},
annote = {Keywords: Circuit complexity, correlations, exponential sums}
}
15.01.2008
Keywords: 

Circuit complexity, correlations, exponential sums 
Seminar: 

07411  Algebraic Methods in Computational Complexity

Issue date: 

2008 
Date of publication: 

15.01.2008 