Lower Bounds for DeMorgan Circuits of Bounded Negation Width

DOI10.4230/LIPIcs.STACS.2019.41OpenAlexW2934762734MaRDI QIDQ5090491

Stasys P. Jukna, Andrzej Lingas

Publication date: 18 July 2022

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

zbMATH Keywords

monotone circuitslower boundsBoolean circuits

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Lower bounds for Boolean circuits of bounded negation width ⋮ On the mystery of negations in circuits: structure vs power

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• Lower bounds on monotone complexity of the logical permanent
• The monotone circuit complexity of Boolean functions
• Efficient monotone circuits for threshold functions
• The gap between monotone and non-monotone circuit complexity is exponential
• Relating monotone formula size and monotone depth of Boolean functions
• Gaussian elimination is not optimal
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Higher lower bounds on monotone size
• Monotone circuits for matching require linear depth
• Depth Lower Bounds against Circuits with Sparse Orientation*
• Bounds on Monotone Switching Networks for Directed Connectivity
• The Potential of the Approximation Method
• Strongly exponential lower bounds for monotone computation
• The Power of Negations in Cryptography
• Learning circuits with few negations
• Multiplying matrices faster than coppersmith-winograd
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Combinatorics of monotone computations

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