### 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.

Original language | English (US) |
---|---|

Pages (from-to) | 257-272 |

Number of pages | 16 |

Journal | Information and Computation |

Volume | 112 |

Issue number | 2 |

DOIs | |

State | Published - Aug 1 1994 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics

### Cite this

*Information and Computation*,

*112*(2), 257-272. https://doi.org/10.1006/inco.1994.1059

}

*Information and Computation*, vol. 112, no. 2, pp. 257-272. https://doi.org/10.1006/inco.1994.1059

**Approximating threshold circuits by rational functions.** / Paturi, Ramamohan; Saks, Michael E.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Approximating threshold circuits by rational functions

AU - Paturi, Ramamohan

AU - Saks, Michael E.

PY - 1994/8/1

Y1 - 1994/8/1

N2 - 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 Ω(n2/ln2n) 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 Ω(n1.2/ln5/3n) edges to compute parity. On the other hand, we give a construction of a depth d threshold circuit that computes parity with n1+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.

AB - 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 Ω(n2/ln2n) 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 Ω(n1.2/ln5/3n) edges to compute parity. On the other hand, we give a construction of a depth d threshold circuit that computes parity with n1+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.

UR - http://www.scopus.com/inward/record.url?scp=0038384211&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0038384211&partnerID=8YFLogxK

U2 - 10.1006/inco.1994.1059

DO - 10.1006/inco.1994.1059

M3 - Article

AN - SCOPUS:0038384211

VL - 112

SP - 257

EP - 272

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - 2

ER -