A spectral technique for random satisfiable 3CNF formulas

DOI10.1002/rsa.20213zbMath1140.68404OpenAlexW4255293738MaRDI QIDQ3514702

Abraham D. Flaxman

Publication date: 21 July 2008

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20213

zbMATH Keywords

satisfiabilityaverage-case analysisspectral algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (3)

Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas ⋮ Cryptographic hardness of random local functions. Survey ⋮ Solving non-uniform planted and filtered random SAT formulas greedily

Cites Work

• Many hard examples for resolution
• Solving random satisfiable 3CNF formulas in expected polynomial time
• Unnamed Item
• Unnamed Item

This page was built for publication: A spectral technique for random satisfiable 3CNF formulas