Lower bounds for monotone \(q\)-multilinear Boolean circuits

DOI10.1007/978-3-031-23101-8_20zbMath1528.94128OpenAlexW4311946266MaRDI QIDQ6169535

Andrzej Lingas

Publication date: 14 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-23101-8_20

zbMATH Keywords

circuit sizemonotone arithmetic circuitmonotone Boolean circuitmonotone multilinear Boolean circuit

Mathematics Subject Classification ID

Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on monotone complexity of the logical permanent
• The monotone circuit complexity of Boolean functions
• Complexity of monotone networks for Boolean matrix product
• Monotone switching circuits and Boolean matrix product
• A lower bound on the number of additions in monotone computations
• On the incompressibility of monotone DNFs
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• The Power of Negative Thinking in Multiplying Boolean Matrices
• Monotone circuits for matching require linear depth
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Multi-linear formulas for permanent and determinant are of super-polynomial size

This page was built for publication: Lower bounds for monotone \(q\)-multilinear Boolean circuits