Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits

DOI10.1007/3-540-62034-6_58MaRDI QIDQ6567780zbMATH OpenFDO

Authors Rimli Sengupta, H. Venkateswaran

Publication date 5 July 2024

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06)

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

Cites work

• scientific article; zbMATH DE number 4058817 (Why is no real title available?)
• scientific article; zbMATH DE number 176507 (Why is no real title available?)
• scientific article; zbMATH DE number 3273218 (Why is no real title available?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Circuit Definitions of Nondeterministic Complexity Classes
• Gaussian elimination is not optimal
• Lower bounds on monotone complexity of the logical permanent
• Monotone versus positive
• Negation can be exponentially powerful
• Nondeterministic Space is Closed under Complementation
• On the complexity of negation-limited Boolean networks (preliminary version)
• The complexity of computing the permanent
• The ellipsoid method and its consequences in combinatorial optimization
• The gap between monotone and non-monotone circuit complexity is exponential
• The monotone circuit complexity of Boolean functions
• Two Applications of Inductive Counting for Complementation Problems

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)