A method for obtaining efficient lower bounds for monotone complexity
From MaRDI portal
Publication:1112792
DOI10.1007/BF01978380zbMath0659.94020MaRDI QIDQ1112792
Publication date: 1987
Published in: Algebra and Logic (Search for Journal in Brave)
Related Items
Lower bounds for tropical circuits and dynamic programs, A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem], Monotone circuit lower bounds from robust sunflowers
Cites Work
- Lower bounds on monotone complexity of the logical permanent
- Some remarks on Boolean sums
- Switching functions whose monotone complexity is nearly quadratic
- Complexity of monotone networks for Boolean matrix product
- Monotone switching circuits and Boolean matrix product
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item