Approximating threshold circuits by rational functions

Ramamohan Paturi, Michael Saks

Research output: Contribution to journalArticle

23 Citations (Scopus)

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
Externally publishedYes

Fingerprint

Threshold Circuits
Rational function
Parity
Golden ratio
Rational Approximation
Boolean Functions
Trade-offs
Lower bound
Computing

All Science Journal Classification (ASJC) codes

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

Cite this

Paturi, Ramamohan ; Saks, Michael. / Approximating threshold circuits by rational functions. In: Information and Computation. 1994 ; Vol. 112, No. 2. pp. 257-272.
@article{f10912cefdf1499a858498704b62d6e2,
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 Ω(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.",
author = "Ramamohan Paturi and Michael Saks",
year = "1994",
month = "8",
day = "1",
doi = "https://doi.org/10.1006/inco.1994.1059",
language = "English (US)",
volume = "112",
pages = "257--272",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Elsevier Inc.",
number = "2",

}

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

In: Information and Computation, Vol. 112, No. 2, 01.08.1994, p. 257-272.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Approximating threshold circuits by rational functions

AU - Paturi, Ramamohan

AU - Saks, Michael

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 - https://doi.org/10.1006/inco.1994.1059

DO - https://doi.org/10.1006/inco.1994.1059

M3 - Article

VL - 112

SP - 257

EP - 272

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - 2

ER -