Note on strong refutation algorithms for random k-SAT formulas

DOI10.1016/J.ENDM.2009.11.027MaRDI QIDQ2840534zbMATH OpenOpenAlexFDO

Authors Hiệp Hàn, Yury Person, M. Schacht

Publication date 19 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2009.11.027

Mathematics Subject Classification ID

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

Recommendations

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Strong Refutation Heuristics for Random k-SAT
• Automata, Languages and Programming
• A better algorithm for random \(k\)-SAT
• scientific article; zbMATH DE number 5899254

Cites work

• scientific article; zbMATH DE number 5899254 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• An efficient sparse regularity concept
• Strong Refutation Heuristics for Random k-SAT
• Weak quasi-randomness for uniform hypergraphs

Cited in

(7)

• On the complexity of random satisfiability problems with planted solutions
• Strongly refuting random CSPs below the spectral threshold
• Automata, Languages and Programming
• Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
• scientific article; zbMATH DE number 7758304 (Why is no real title available?)
• Strong Refutation Heuristics for Random k-SAT
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Note on strong refutation algorithms for random \(k\)-SAT formulas

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