Paper Info
Title
Approximating threshold circuits by rational functions
Abstract
Motivated by the problem of understanding the limitations of threshold networks for representing boolean functions, we consider size-depth trade-offs for threshold circuits that compute the parity function. Using a fundamental result in the theory of rational approximation, we show how to approximate small threshold circuits by rational functions of low degree. We apply this result to establish an almost optimal lower bound of Ω ( n 2 /ln 2 n ) on the number of edges of any depth-2 threshold circuit with polynomially bounded weights that computes the parity function. We also prove that any depth-3 threshold circuit with polynomially bounded weights requires Ω ( n 1.2 /ln 5/3 n ) edges to compute parity. On the other hand, we give a construction of a depth d threshold circuit that computes parity with n 1+1/ Θ (φ d ) edges where φ = (1 + √5)/2 is the golden ratio. We conjecture that there are no linear size bounded depth threshold circuits for computing parity.
Year
DOI
Venue
1994
10.1006/inco.1994.1059
Inf. Comput.
Keywords
Field
DocType
approximating threshold circuit,rational function
Boolean function,Discrete mathematics,Combinatorics,Upper and lower bounds,Parity function,Golden ratio,Rational function,Parity (mathematics),Conjecture,Mathematics,Bounded function
Journal
Volume
Issue
ISSN
112
2
Information and Computation
Citations 
PageRank 
References 
21
1.38
11
Authors
2
Name
Order
Citations
PageRank
Ramamohan Paturi1126092.20
Michael Saks22595302.11