__
TR95-027 | 30th May 1995 00:00
__

#### Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate

**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.