Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
From MaRDI portal
Publication:3191968
DOI10.1145/335305.335309zbMath1296.68062OpenAlexW2128782263MaRDI QIDQ3191968
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (23)
A sharp threshold for a random constraint satisfaction problem ⋮ A sharp threshold in proof complexity yields lower bounds for satisfiability search ⋮ An algorithm for random signed 3-SAT with intervals ⋮ On threshold properties of \(k\)-SAT: An additive viewpoint ⋮ Phase transitions of PP-complete satisfiability problems ⋮ Phase transition in a random NK landscape model ⋮ On good algorithms for determining unsatisfiability of propositional formulas ⋮ On the Method of Typical Bounded Differences ⋮ Analysis of greedy algorithms on graphs with bounded degrees ⋮ On the average similarity degree between solutions of random \(k\)-SAT and random CSPs. ⋮ The cook-book approach to the differential equation method ⋮ Branching Process Approach for 2-Sat Thresholds ⋮ Space complexity of random formulae in resolution ⋮ Rigorous results for random (\(2+p)\)-SAT ⋮ Random 2-SAT: Results and problems ⋮ Results related to threshold phenomena research in satisfiability: Lower bounds ⋮ Lower bounds for random 3-SAT via differential equations ⋮ Upper bounds on the satisfiability threshold ⋮ Almost all graphs with average degree 4 are 3-colorable ⋮ Super solutions of random \((3 + p)\)-SAT ⋮ When does the giant component bring unsatisfiability? ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ Selecting Complementary Pairs of Literals
This page was built for publication: Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
