Average-case lower bounds for formula size

DOI10.1145/2488608.2488630zbMath1293.68147OpenAlexW2030586582MaRDI QIDQ5495787

Ilan Komargodski, Ran Raz

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsBoolean formulasDe Morgan formulasaverage-case hardnesscorrelation bounds

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (15)

Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ An improved deterministic \#SAT algorithm for small De Morgan formulas ⋮ Correlation bounds and \#SAT algorithms for small linear-size circuits ⋮ Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits ⋮ Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases ⋮ Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Unnamed Item ⋮ Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Fourier concentration from shrinkage ⋮ Negation-limited formulas ⋮ Cubic Formula Size Lower Bounds Based on Compositions with Majority ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Mining circuit lower bound proofs for meta-algorithms

This page was built for publication: Average-case lower bounds for formula size