A Well-Mixed Function with Circuit Complexity 5n ±o(n): Tightness of the Lachish-Raz-Type Bounds
From MaRDI portal
Publication:3502659
DOI10.1007/978-3-540-79228-4_30zbMath1139.94303MaRDI QIDQ3502659
Publication date: 27 May 2008
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-79228-4_30
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Entropy of contact circuits and lower bounds on their complexity
- A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
- The polynomial method and restricted sums of congruence classes
- A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
- Asymptotically Optimal Circuit for a Storage Access Function
- Cyclic Spaces for Grassmann Derivatives and Additive Theory
- Explicit lower bound of 4.5n - o(n) for boolena circuits