Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound

DOI10.1137/15M1048045zbMath1376.03043OpenAlexW2585952665MaRDI QIDQ2963581

Ilan Komargodski, Ran Raz, Avishay Tal

Publication date: 15 February 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/15m1048045

zbMATH Keywords

shrinkageBoolean formulasaverage-case lower bound

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Quantified Derandomization: How to Find Water in the Ocean ⋮ Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases ⋮ Algorithms and lower bounds for comparator circuits from shrinkage ⋮ 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 ⋮ Unnamed Item ⋮ Improved Extractors for Recognizable and Algebraic Sources ⋮ Fourier concentration from shrinkage ⋮ Cubic Formula Size Lower Bounds Based on Compositions with Majority ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression

Cites Work

• Boolean function complexity. Advances and frontiers.
• On the construction of affine extractors
• A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
• Mining circuit lower bound proofs for meta-algorithms
• Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
• The Shrinkage Exponent of de Morgan Formulas is 2
• The effect of random restrictions on formula size
• Shrinkage of de Morgan formulae under restriction
• Pseudorandomness from Shrinkage
• Probability Inequalities for Sums of Bounded Random Variables
• Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
• Quantum lower bounds by polynomials
• Average-case lower bounds for formula size
• Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound