Boolean circuit complexity and two-dimensional cover problems

DOI10.1145/3718746MaRDI QIDQ6949655zbMATH OpenFDO

Authors Bruno Pasqualotto Cavalar, Igor C. Oliveira

Publication date 1 August 2025

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3718746

zbMATH Keywords

Boolean circuitscomplexity lower boundsfusion methodgraph complexity

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• 3.1 n − o ( n ) circuit lower bounds for explicit functions
• A better-than-3n lower bound for the circuit complexity of an explicit function
• Boolean function complexity. Advances and frontiers.
• Computational complexity of graphs
• Graph complexity
• Graph complexity and slice functions
• scientific article; zbMATH DE number 4108153 (Why is no real title available?)
• scientific article; zbMATH DE number 524142 (Why is no real title available?)
• On the complexity of Boolean matrices, graphs, and the Boolean functions corresponding to them
• On the limits of gate elimination
• On the number of ANDs versus the number of ORs in monotone Boolean circuits
• Separation of the monotone NC hierarchy
• The monotone circuit complexity of Boolean functions

This page was built for publication: Boolean circuit complexity and two-dimensional cover problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6949655)