Lower bounds for monotone q-multilinear Boolean circuits
From MaRDI portal
Publication:6169535
DOI10.1007/978-3-031-23101-8_20zbMATH Open1528.94128OpenAlexW4311946266MaRDI QIDQ6169535FDOQ6169535
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
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
- Complexity of monotone networks for Boolean matrix product
- Monotone switching circuits and Boolean matrix product
- The Power of Negative Thinking in Multiplying Boolean Matrices
- Thin circulant matrices and lower bounds on complexity of some Boolean operators
- A lower bound on the number of additions in monotone computations
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- The monotone circuit complexity of Boolean functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lower bounds on monotone complexity of the logical permanent
- Monotone circuits for matching require linear depth
- On the incompressibility of monotone DNFs
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Title not available (Why is that?)
Cited In (4)
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)
