 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/
 Go to the corresponding Portal

### Uniqueness of Optimal Mod 3 Circuits for Parity

 pdf-format:

### 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 | Privacy 