Computer Science

A complex-number Fourier technique for lower bounds on the mod-m degree

Document Type

Article

Abstract

We say an integer polynomial p, on Boolean inputs, weakly m-represents a Boolean function f if p is nonconstant and is zero (mod m), whenever f is zero. In this paper we prove that if a polynomial weakly m-represents the Modq function on n inputs, where q and m are relatively prime and m is otherwise arbitrary, then the degree of the polynomial is Ω(n). This generalizes previous results of Barrington, Beigel and Rudich, and Tsai, 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) 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 that computes the Modq function, and consists of an exact threshold gate at the output, Modp 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.

Publication Title

Computational Complexity

Publication Date

2000

Volume

9

Issue

1

First Page

16

Last Page

38

ISSN

1016-3328

DOI

10.1007/PL00001599

Keywords

circuit complexity, Fourier methods, lower bounds, Modulo functions

APA Citation

Green, F. (2000). A complex-number Fourier technique for lower bounds on the mod-m degree. Computational Complexity, 9, 16-38.

Link to Full Text

Share

COinS