Approximating threshold circuits by rational functions

Ramamohan Paturi, Michael E. Saks

Research output: Contribution to journalArticle

23 Scopus citations

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 Ω(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.

Original languageEnglish (US)
Pages (from-to)257-272
Number of pages16
JournalInformation and Computation
Volume112
Issue number2
DOIs
StatePublished - Aug 1 1994

    Fingerprint

All Science Journal Classification (ASJC) codes

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

Cite this