Random Structures and Algorithms · 1995 · 114 citations · 9 references
ComputingComputer ScienceMathematicsAlgorithmsDiscrete MathematicsTheory Of ComputationConstraint SatisfactionRandomized ComputationBoolean SatisfiabilityBoolean Satisfiability ProblemComplexity Of SatisfiabilityProbabilistic AnalysisSatisfiabilitySatisfiability ProblemTail BoundsUnsatisfiability
Abstract The classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation of m balls to n bins. We provide a series of tail bounds on the distribution of the number of empty bins. These tail bounds should find application in randomized algorithms and probabilistic analysis. Our motivating application is the following well‐known conjecture on threshold phenomenon for the satisfiability problem. Consider random 3‐SAT formulas with cn clauses over n variables, where each clause is chosen uniformly and independently from the space of all clauses of size 3. It has been conjectured that there is a sharp threshold for satisfiability at c * ≈︁ 4.2. We provide a strong upper bound on the value of c *, showing that for c > 4.758 a random 3‐SAT formula is unsatisfiable with high probability. This result is based on a structural property, possibly of independent interest, whose proof needs several applications of the occupancy tail bounds.
9
Weighted sums of certain dependent random variables
Kazuoki Azuma · Tohoku Mathematical Journal · 1967 · 1.1K citations · Full text
Many hard examples for resolution
Vašek Chvátal, Endre Szemerédi · Journal of the ACM · 1988 · 445 citations · Full text
A Threshold for Unsatisfiability
Andreas Goerdt · Journal of Computer and System Sciences · 1996 · 240 citations
Mick gets some (the odds are on his side) (satisfiability)
Vašek Chvátal, Bruce Reed · 1992 · 215 citations