Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)

DOI10.1145/335305.335309MaRDI QIDQ3191968zbMATH OpenOpenAlexFDO

Authors D. Achlioptas

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/335305.335309

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Bounding the unsatisfiability threshold of random 3-SAT
• A new upper bound for 3-SAT
• On Random 3-sat
• On the satisfiability threshold of formulas with three literals per clause
• Lower bounds for random 3-SAT via differential equations

Cited in

(27)

• Super solutions of random \((3 + p)\)-SAT
• A sharp threshold for a random constraint satisfaction problem
• Almost all graphs with average degree 4 are 3-colorable
• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• On good algorithms for determining unsatisfiability of propositional formulas
• On threshold properties of k-SAT: An additive viewpoint
• On the average similarity degree between solutions of random \(k\)-SAT and random CSPs.
• Branching process approach for 2-SAT thresholds
• On the Lower Bounds of Random Max 3 and 4-SAT
• Upper bounds on the satisfiability threshold
• An algorithm for random signed 3-SAT with intervals
• Rigorous results for random (\(2+p)\)-SAT
• Results related to threshold phenomena research in satisfiability: Lower bounds
• The cook-book approach to the differential equation method
• On the method of typical bounded differences
• Phase transition in a random NK landscape model
• Lower bounds for random 3-SAT via differential equations
• Random 2-SAT: Results and problems
• Analysis of greedy algorithms on graphs with bounded degrees
• Phase transitions of PP-complete satisfiability problems
• AI 2003: Advances in Artificial Intelligence
• On Random 3-sat
• A sharp threshold in proof complexity yields lower bounds for satisfiability search
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• When does the giant component bring unsatisfiability?
• Selecting Complementary Pairs of Literals
• Space complexity of random formulae in resolution

This page was built for publication: Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)

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