Loading...
Please wait, while we are loading the content...
Similar Documents
Complex Fourier Technique for Lower Bounds on the Mod-m Degree Revised and Expanded Version of \lower Bounds for Depth-three Circuits with Equals and Mod-gates," in 12th Annual Symposium on Theoretical
| Content Provider | Semantic Scholar |
|---|---|
| Author | Green, Frederic |
| 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 Mod q function on n inputs, where q and m are relatively prime and m is otherwise arbitrary, then the degree of the polynomial is (n). which held only for constant or slowly growing m. In addition, the proof technique given here is quite diierent. We use a method (adapted from 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 which computes the Mod q function, and consists of an exact threshold gate at the output, Mod p-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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.researchgate.net/profile/Frederic_Green/publication/225707893_A_complex-number_Fourier_technique_for_lower_bounds_on_the_Mod-m_degree/links/00b4951f01356b5059000000.pdf |
| Alternate Webpage(s) | http://math-gw.clarku.edu/~fgreen/papers/fourier.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
