Size--Depth Tradeoffs for Threshold Circuits

DOI10.1137/S0097539792282965zbMATH Open0870.68069OpenAlexW2001187993MaRDI QIDQ4337668FDOQ4337668

Authors Russell Impagliazzo, Ramamohan Paturi, Michael Saks

Publication date 26 May 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539792282965

zbMATH Keywords

lower boundscircuit complexitythreshold circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Approximating threshold circuits by rational functions
• The complexity of computing symmetric functions using threshold circuits
• scientific article; zbMATH DE number 1256716

Cited in

(33)

• On the power of small-depth threshold circuits
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Quantified Derandomization: How to Find Water in the Ocean
• Neural networks with linear threshold activations: structure and algorithms
• Hardness magnification near state-of-the-art lower bounds
• Uniform derandomization from pathetic lower bounds
• Affine projections of symmetric polynomials.
• Depth lower bounds against circuits with sparse orientation
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Impossibility results for weak threshold networks
• On the power of a threshold gate at the top
• Energy and depth of threshold circuits
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
• Exponential lower bound for bounded depth circuits with few threshold gates
• Hardness magnification near state-of-the-art lower bounds
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• scientific article; zbMATH DE number 773999 (Why is no real title available?)
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Size and Energy of Threshold Circuits Computing Mod Functions
• Bootstrapping results for threshold circuits ``just beyond known lower bounds
• Decomposition of threshold functions into bounded fan-in threshold functions
• Threshold circuits of small majority-depth
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
• Majority gates vs. general weighted threshold gates
• Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
• Size-energy tradeoffs for unate circuits computing symmetric Boolean functions
• Quadratization of symmetric pseudo-Boolean functions
• Size, Depth and Energy of Threshold Circuits Computing Parity Function.
• Local reduction
• Mathematical Foundations of Computer Science 2005
• A super-quadratic lower bound for depth four arithmetic circuits
• scientific article; zbMATH DE number 4003533 (Why is no real title available?)

This page was built for publication: Size--Depth Tradeoffs for Threshold Circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4337668)