Lower Bounds for DeMorgan Circuits of Bounded Negation Width

DOI10.4230/LIPICS.STACS.2019.41MaRDI QIDQ5090491zbMATH OpenOpenAlexFDO

Authors Stasys Jukna, Andrzej Lingas

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/lipics.stacs.2019.41

zbMATH Keywords

Boolean circuitslower boundsmonotone circuits

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Lower bounds for Boolean circuits of bounded negation width
• Limiting Negations in Constant Depth Circuits
• scientific article; zbMATH DE number 176507
• Algorithms and Computation
• Limiting negations in bounded treewidth and upward planar circuits

Cites work

• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Boolean function complexity. Advances and frontiers.
• Bounds on Monotone Switching Networks for Directed Connectivity
• Combinatorics of monotone computations
• Depth lower bounds against circuits with sparse orientation
• Efficient monotone circuits for threshold functions
• Gaussian elimination is not optimal
• Higher lower bounds on monotone size
• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 3715454 (Why is no real title available?)
• scientific article; zbMATH DE number 3788540 (Why is no real title available?)
• scientific article; zbMATH DE number 6829287 (Why is no real title available?)
• scientific article; zbMATH DE number 7250166 (Why is no real title available?)
• Learning circuits with few negations
• Lower bounds on monotone complexity of the logical permanent
• Monotone circuits for matching require linear depth
• Multiplying matrices faster than coppersmith-winograd
• Relating monotone formula size and monotone depth of Boolean functions
• Strongly exponential lower bounds for monotone computation
• The gap between monotone and non-monotone circuit complexity is exponential
• The monotone circuit complexity of Boolean functions
• The Potential of the Approximation Method
• The power of negations in cryptography

Cited in

(3)

• On the mystery of negations in circuits: structure vs power
• Limiting negations in bounded-depth circuits: an extension of Markov's theorem
• Lower bounds for Boolean circuits of bounded negation width

This page was built for publication: Lower Bounds for DeMorgan Circuits of Bounded Negation Width

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