Average-case lower bounds for formula size

DOI10.1145/2488608.2488630MaRDI QIDQ5495787zbMATH OpenOpenAlexFDO

Authors Ilan Komargodski, Ran Raz

Publication date 7 August 2014

Published in Proceedings of the forty-eighth 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

average-case hardnessBoolean formulascorrelation boundsDe Morgan formulaslower bounds

Mathematics Subject Classification ID

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

Recommendations

• An n! lower bound on formula size
• Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
• Breaking the rectangle bound barrier against formula size lower bounds
• Breaking the rectangle bound barrier against formula size lower bounds
• A Lower Bound for the Formula Size of Rational Functions
• Cubic Formula Size Lower Bounds Based on Compositions with Majority
• scientific article; zbMATH DE number 1564047
• A New Rank Technique for Formula Size Lower Bounds
• On lower bounds on the size of sums-of-squares formulas
• Lower bound results on lengths of second-order formulas

Cited in

(18)

• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Fourier concentration from shrinkage
• Mining circuit lower bound proofs for meta-algorithms
• Satisfiability algorithms and lower bounds for Boolean formulas over finite bases
• Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• An improved deterministic \#SAT algorithm for small De Morgan formulas
• Correlation bounds and \#SAT algorithms for small linear-size circuits
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Formula lower bounds via the quantum method
• Small bias requires large formulas
• Quantified Derandomization: How to Find Water in the Ocean
• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
• Cubic Formula Size Lower Bounds Based on Compositions with Majority
• Algorithms and lower bounds for comparator circuits from shrinkage
• Shrinkage of decision lists and DNF formulas
• Negation-limited formulas

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495787)