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

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.

Link to Full Text

Share

COinS