scientific article

DOI10.4086/toc.2007.v003a002zbMath1213.68329OpenAlexW269572962MaRDI QIDQ3002778

Eran Ofek

Publication date: 24 May 2011

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2007.v003a002

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

spectral methodproof complexityaverage case analysisrefutationBoolean formula3CNF

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20)

Related Items (6)

Noisy tensor completion via the sum-of-squares hierarchy ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Towards strong nonapproximability results in the Lovász-Schrijver hierarchy ⋮ Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ Note on strong refutation algorithms for random k-SAT formulas

This page was built for publication: