Tail bounds for occupancy and the satisfiability threshold conjecture

摘要: The classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation m balls to n bins. We provide series tail bounds on distribution These should find application in randomized algorithms and probabilistic analysis. Our motivating following well-known conjecture threshold phenomenon for satisfiability problem. Consider 3-SAT formulas cn clauses over variables, where each clause chosen uniformly independently space all size 3. It has been conjectured that there sharp at c*/spl ap/4.2. first non-trivial upper bound value c*, showing c>4.758 formula unsatisfiable high probability. This result based structural property, possibly independent interest, whose proof needs several applications bounds. >