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

## Repository Citation

Green, Frederic, "A complex-number Fourier technique for lower bounds on the mod-m degree" (2000). *Computer Science*. 64.

https://commons.clarku.edu/faculty_computer_sciences/64

## APA Citation

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