Lower Bounds for DeMorgan Circuits of Bounded Negation Width
From MaRDI portal
Publication:5090491
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
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
