## Computer Science

# Lower bounds for depth-three circuits with equals and mod-gates

## Document Type

Conference Paper

## 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 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 [BBa] and Wsai [Tsai], which held only for constant (or slowly growing) m. The proof technique given here is quite different and somewhat simpler. We use a method in which the inputs are represented as complex qth roots of unity (following Barrington and Straubing [BS]). The representation is used to take advantage of a variant of the inverse Fourier transform and 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 Modq function, and consists of an equals gate at the output, Modp-gates at the next level, and AND-gates of small fan-in at the inputs, must be of exponential size. In terms of Turing machine complexity classes, there is an oracle A such that ModqPA (image found) C=PModPPA.

## Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

## Publication Date

1995

## Volume

900

## First Page

71

## Last Page

82

## ISSN

0302-9743

## ISBN

9783540590422

## DOI

10.1007/3-540-59042-0_63

## Repository Citation

Green, Frederic, "Lower bounds for depth-three circuits with equals and mod-gates" (1995). *Computer Science*. 73.

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

## APA Citation

Green, F. (1995, March). Lower bounds for depth-three circuits with equals and mod-gates. In *Annual Symposium on Theoretical Aspects of Computer Science* (pp. 71-82). Berlin, Heidelberg: Springer Berlin Heidelberg.