Lower bounds for monotone q-multilinear Boolean circuits

DOI10.1007/978-3-031-23101-8_20MaRDI QIDQ6169535zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Towards an almost quadratic lower bound on the monotone circuit complexity of the Boolean convolution
• Algorithms and Computation
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• The monotone circuit complexity of quadratic Boolean functions
• On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions

Cites work

• A lower bound on the number of additions in monotone computations
• Complexity of monotone networks for Boolean matrix product
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 7250166 (Why is no real title available?)
• Lower bounds on monotone complexity of the logical permanent
• Monotone circuits for matching require linear depth
• Monotone switching circuits and Boolean matrix product
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• On the incompressibility of monotone DNFs
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• The monotone circuit complexity of Boolean functions
• The Power of Negative Thinking in Multiplying Boolean Matrices
• Thin circulant matrices and lower bounds on complexity of some Boolean operators

Cited in

(4)

• An exponential lower bound for the size of monotone real circuits
• scientific article; zbMATH DE number 6007880 (Why is no real title available?)
• scientific article; zbMATH DE number 1222575 (Why is no real title available?)
• Monotone circuit lower bounds from robust sunflowers

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

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