Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
From MaRDI portal
Publication:1566723
DOI10.1016/S0304-3975(98)00170-4zbMath0939.68043MaRDI QIDQ1566723
H. Venkateswaran, Rimli Sengupta
Publication date: 4 June 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Lower bounds on monotone complexity of the logical permanent
- The monotone circuit complexity of Boolean functions
- Negation can be exponentially powerful
- The ellipsoid method and its consequences in combinatorial optimization
- A very hard log-space counting class
- The gap between monotone and non-monotone circuit complexity is exponential
- Superpolynomial lower bounds for monotone span programs
- Separation of the monotone NC hierarchy
- Gaussian elimination is not optimal
- On the complexity of negation-limited Boolean networks
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Monotone versus positive
- Nondeterministic Space is Closed under Complementation
- Two Applications of Inductive Counting for Complementation Problems
- Structure and importance of logspace-MOD class
- Circuit Definitions of Nondeterministic Complexity Classes
- Monotone circuits for matching require linear depth
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
