Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits
From MaRDI portal
Publication:6567780
DOI10.1007/3-540-62034-6_58zbMATH Open1541.68138MaRDI QIDQ6567780FDOQ6567780
Authors: Rimli Sengupta, H. Venkateswaran 
Publication date: 5 July 2024
Recommendations
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
- Cancellation is exponentially powerful for computing the determinant
- Cancellation-free circuits in unbounded and bounded depth
- scientific article; zbMATH DE number 176871
- Cancellation-free circuits in unbounded and bounded depth
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06)
Cites Work
- The complexity of computing the permanent
- The ellipsoid method and its consequences in combinatorial optimization
- Gaussian elimination is not optimal
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Nondeterministic Space is Closed under Complementation
- Negation can be exponentially powerful
- The monotone circuit complexity of Boolean functions
- Lower bounds on monotone complexity of the logical permanent
- The gap between monotone and non-monotone circuit complexity is exponential
- On the complexity of negation-limited Boolean networks (preliminary version)
- Two Applications of Inductive Counting for Complementation Problems
- Monotone versus positive
- Title not available (Why is that?)
- Circuit Definitions of Nondeterministic Complexity Classes
- Title not available (Why is that?)
- Title not available (Why is that?)
This page was built for publication: Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6567780)
