License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-13059
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1305/
Green, Frederic ; Roy, Amitabha

Uniqueness of Optimal Mod 3 Circuits for Parity

pdf-format:
Dokument 1.pdf (213 KB)

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 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 $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:DSP:2008:1305,
  author =	{Frederic Green and Amitabha Roy},
  title =	{Uniqueness of Optimal Mod 3 Circuits  for Parity},
  booktitle =	{Algebraic Methods in Computational Complexity},
  year =	{2008},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  number =	{07411},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1305},
  annote =	{Keywords: Circuit complexity, correlations, exponential sums}
}

Keywords: Circuit complexity, correlations, exponential sums
Seminar: 07411 - Algebraic Methods in Computational Complexity
Issue date: 2008
Date of publication: 15.01.2008

DROPS-Home | Fulltext Search | Imprint Published by LZI