Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
- 1 May 2000
- conference paper
- Published by Association for Computing Machinery (ACM)
Abstract
No abstract availableKeywords
This publication has 24 references indexed in Scilit:
- Tricritical points in random combinatorics: the -SAT caseJournal of Physics A: General Physics, 1998
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT FormulaeJournal of Algorithms, 1997
- Statistical mechanics of the random-satisfiability modelPhysical Review E, 1997
- Entropy of theK-Satisfiability ProblemPhysical Review Letters, 1996
- Analysis of Two Simple Heuristics on a Random Instance ofk-satJournal of Algorithms, 1996
- Differential Equations for Random Processes and Random GraphsThe Annals of Applied Probability, 1995
- Tail bounds for occupancy and the satisfiability threshold conjectureRandom Structures & Algorithms, 1995
- Many hard examples for resolutionJournal of the ACM, 1988
- Probabilistic analysis of the pure literal heuristic for the satisfiability problemAnnals of Operations Research, 1984
- Solutions of ordinary differential equations as limits of pure jump markov processesJournal of Applied Probability, 1970