文章基本信息

标题：Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate
本地全文：下载
作者：Frederic Green
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 (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 qth 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 qp are distinct primes, any depth-three circuit which 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 12+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.
关键词：circuit complexity, Computational Complexity