Explicit lower bound of 4.5n - o(n) for boolena circuits

DOI10.1145/380752.380832zbMath1323.68303OpenAlexW2056017973MaRDI QIDQ5175995

Oded Lachish, Ran Raz

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380832

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (24)

Local Reductions ⋮ The complexity of depth-3 circuits computing symmetric Boolean functions ⋮ Local reduction ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Correlation bounds and \#SAT algorithms for small linear-size circuits ⋮ Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits ⋮ Lower Bounds for the Size of Nondeterministic Circuits ⋮ A Well-Mixed Function with Circuit Complexity 5n ±o(n): Tightness of the Lachish-Raz-Type Bounds ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds ⋮ Feebly secure cryptographic primitives ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ On the power of nondeterministic circuits and co-nondeterministic circuits ⋮ Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ Reductions for monotone Boolean circuits ⋮ Almost-natural proofs ⋮ Negation-limited formulas ⋮ Unnamed Item ⋮ Negation-limited complexity of parity and inverters ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ New lower bounds on circuit size of multi-output functions

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: Explicit lower bound of 4.5n - o(n) for boolena circuits