Polynomial size constant depth circuits with a limited number of negations

DOI10.1007/BFB0020801MaRDI QIDQ4035672zbMATH OpenFDO

Authors Miklos Santha, Christopher B. Wilson

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0020801

zbMATH Keywords

Boolean functioncircuitfan-in circuitsthreshold circuits

Mathematics Subject Classification ID

Recommendations

• Limiting Negations in Constant Depth Circuits
• On the Complexity of Negation-Limited Boolean Networks
• Algorithms and Computation
• Limiting negations in bounded-depth circuits: an extension of Markov's theorem
• Negation-limited circuit complexity of symmetric functions

Cited in

(14)

• On the minimum number of negations leading to super-polynomial savings
• Linear-size constant-depth polylog-threshold circuits
• Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
• Limiting negations in bounded-depth circuits: an extension of Markov's theorem
• Lower bounds for Boolean circuits of bounded negation width
• On the positive and the inversion complexity of Boolean functions
• Limiting negations in bounded treewidth and upward planar circuits
• scientific article; zbMATH DE number 89639 (Why is no real title available?)
• Limiting Negations in Constant Depth Circuits
• Lower Bounds for DeMorgan Circuits of Bounded Negation Width
• Algorithms and Computation
• Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits
• Negation-limited formulas
• Lower bounds for constant-depth circuits in the presence of help bits

This page was built for publication: Polynomial size constant depth circuits with a limited number of negations

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