  Under the auspices of the Computational Complexity Foundation (CCF)     REPORTS > DETAIL:

### Paper:

TR95-027 | 30th May 1995 00:00

#### Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate TR95-027
Authors: Frederic Green
Publication: 9th June 1995 15:11
Keywords:

Abstract:

We say an integer polynomial \$p\$, on Boolean inputs, weakly
\$m\$-represents a Boolean function \$f\$ if \$p\$ is non-constant and is zero (mod
\$m\$), whenever \$f\$ is zero. In this paper we prove that if a polynomial
weakly \$m\$-represents the Mod\$_q\$ function on \$n\$ inputs, where \$q\$ and \$m\$
are relatively prime and \$m\$ is otherwise arbitrary, then the degree of the
polynomial is \$\Omega(n)\$. This generalizes previous results of Barrington,
Beigel and Rudich (STOC 1992, pp. 455-461) and Tsai (Structures 1993,
pp. 96-101), which held only for constant or slowly growing \$m\$. In
addition, the proof technique given here is quite different. We use a
method (adapted from Barrington and Straubing, LATIN '92, pp.~24-31) in
which the inputs are represented as complex \$q^{th}\$ roots of unity.
In this representation it is possible to compute the Fourier transform
using some elementary properties of the algebraic integers. As a corollary of
the main theorem and the proof of Toda's theorem, if \$q,p\$ are distinct
primes, any depth-three circuit which computes the \$\Mod_q\$ function, and
consists of an exact threshold gate at the output, \$\Mod_p\$-gates at the
next level, and AND-gates of polylog fan-in at the inputs, must be of
exponential size. We also consider the question of how well circuits
consisting of one exact gate over ACC(\$p\$)-type circuits (where \$p\$ is an
odd prime) can approximate parity. It is shown that such circuits must have
exponential size in order to agree with parity for more than \$1/2 + o(1)\$
of the inputs.
This is a revised and expanded version of ``Lower Bounds for Depth-Three
Circuits with Equals and Mod-Gates," in STACS 1995, pp. 71-82.

ISSN 1433-8092 | Imprint