Tail bounds for occupancy and the satisfiability threshold conjecture
- 1 August 1995
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 7 (1), 59-80
- https://doi.org/10.1002/rsa.3240070105
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- Randomized AlgorithmsPublished by Cambridge University Press (CUP) ,1995
- A threshold for unsatisfiabilityLecture Notes in Computer Science, 1992
- Mick gets some (the odds are on his side) (satisfiability)Published by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problemInformation Sciences, 1990
- The harmonic mean formula for probabilities of unions: applications to sparse random graphsDiscrete Mathematics, 1989
- Many hard examples for resolutionJournal of the ACM, 1988
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability ProblemSIAM Journal on Computing, 1986
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problemDiscrete Applied Mathematics, 1983
- Mélanges d'équations différentielles et grands écarts à la loi des grands nombresProbability Theory and Related Fields, 1977
- Weighted sums of certain dependent random variablesTohoku Mathematical Journal, 1967