A size-depth trade-off for the analog computation of Boolean functions

DOI10.1016/0020-0190(96)00120-2zbMath1023.68588OpenAlexW1978991428MaRDI QIDQ671617

György Turán, Farrokh Vatan

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00120-2

zbMATH Keywords

computational complexityBoolean functionssize-depth trade-offsarithmetic threshold circuits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

On the computation of Boolean functions by analog circuits of bounded fan-in

Cites Work

• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• Two \(P\)-complete problems in the theory of the reals
• Approximating threshold circuits by rational functions
• Lower bounds for arithmetic networks
• Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
• On Parallel Computation for the Knapsack Problem
• Rational approximation techniques for analysis of neural networks
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Size-depth trade-offs for threshold circuits
• Depth-size tradeoffs for neural computation
• Lower Bounds for Approximation by Nonlinear Manifolds
• On the Betti Numbers of Real Varieties
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item