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

Recommendations

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

zbMATH Keywords

lower boundscircuit complexitythreshold circuits

Mathematics Subject Classification ID

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

Cited In (26)

• Energy and depth of threshold circuits
• Title not available (Why is that?)
• Size-energy tradeoffs for unate circuits computing symmetric Boolean functions
• Quadratization of symmetric pseudo-Boolean functions
• A super-quadratic lower bound for depth four arithmetic circuits
• Threshold circuits of small majority-depth
• Size, Depth and Energy of Threshold Circuits Computing Parity Function.
• Affine projections of symmetric polynomials.
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Exponential lower bound for bounded depth circuits with few threshold gates
• On the power of small-depth threshold circuits
• Local reduction
• Neural networks with linear threshold activations: structure and algorithms
• Majority gates vs. general weighted threshold gates
• Title not available (Why is that?)
• Quantified Derandomization: How to Find Water in the Ocean
• Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
• Title not available (Why is that?)
• Mathematical Foundations of Computer Science 2005
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Size and Energy of Threshold Circuits Computing Mod Functions
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
• Hardness magnification near state-of-the-art lower bounds
• Title not available (Why is that?)
• Uniform derandomization from pathetic lower bounds

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)