{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,23]],"date-time":"2025-11-23T20:56:15Z","timestamp":1763931375237},"reference-count":25,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4089,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1995,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation of <jats:italic>m<\/jats:italic> balls to <jats:italic>n<\/jats:italic> 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\u2010known conjecture on threshold phenomenon for the satisfiability problem. Consider random 3\u2010SAT formulas with <jats:italic>cn<\/jats:italic> clauses over <jats:italic>n<\/jats:italic> 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 <jats:italic>c<\/jats:italic>* \u2248\ufe01 4.2. We provide a strong upper bound on the value of <jats:italic>c<\/jats:italic>*, showing that for <jats:italic>c<\/jats:italic> &gt; 4.758 a random 3\u2010SAT 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.<\/jats:p>","DOI":"10.1002\/rsa.3240070105","type":"journal-article","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T18:48:21Z","timestamp":1180205301000},"page":"59-80","source":"Crossref","is-referenced-by-count":67,"title":["Tail bounds for occupancy and the satisfiability threshold conjecture"],"prefix":"10.1002","volume":"7","author":[{"given":"Anil","family":"Kamath","sequence":"first","affiliation":[]},{"given":"Rajeev","family":"Motwani","sequence":"additional","affiliation":[]},{"given":"Krishna","family":"Palem","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90316-6"},{"key":"e_1_2_1_3_2","volume-title":"The Probabilistic Method","author":"Alon N.","year":"1992"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00534169"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.2748\/tmj\/1178243286"},{"key":"e_1_2_1_6_2","unstructured":"A.Broder A.Frieze andE.Upfal On the satisfiability and maximum satisfiability of random 3\u2010CNF formulas Proc. Fourth ACM\u2010SIAM Symposium on Discrete Algorithms 1993 pp.322\u2013330."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215080"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(90)90030-E"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"V.Chv\u00e1talandB.Reed Mick gets some (the odds are on his side) Proc. 33rd IEEE Symposium on Foundations of Computer Science 1992 pp.620\u2013627.","DOI":"10.1109\/SFCS.1992.267789"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48016"},{"key":"e_1_2_1_11_2","unstructured":"W. Fernandezde la Vega On random 2\u2010SAT manuscript (1992)."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90017-3"},{"key":"e_1_2_1_13_2","unstructured":"A. M.FriezeandS.Suen Analysis of simple heuristics for random instances of 3\u2010SAT manuscript (1993)."},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"A.Goerdt A threshold for unsatisfiability Proc. 7th International Symposium on Mathematical Foundations of Computer Science 1992 pp.264\u2013274.","DOI":"10.1007\/3-540-55808-X_25"},{"key":"e_1_2_1_15_2","unstructured":"A.Goldberg Average case complexity of the satisfiability problem Proc. 4th Workshop on Automated Deduction 1979 pp.1\u20136."},{"key":"e_1_2_1_16_2","volume-title":"Martingale Limit Theory and Its Application","author":"Hall P.","year":"1980"},{"key":"e_1_2_1_17_2","unstructured":"S.Janson Large deviation inequalities for sums of indicator variables Tech. Rep. No. 34 Department of Mathematics Uppsala University 1994."},{"key":"e_1_2_1_18_2","volume-title":"Urn Models and Their Applications","author":"Johnson N. L.","year":"1977"},{"key":"e_1_2_1_19_2","volume-title":"Random Allocations","author":"Kolchin V. F.","year":"1978"},{"key":"e_1_2_1_20_2","unstructured":"T.LarrabeeandY.Tsuji Evidence for satisfiability threshold for random 3CNF formulas Tech. Rep. UCSC\u2010CRL\u201092\u201342 University of California Santa Cruz 1992."},{"key":"e_1_2_1_21_2","first-page":"148","volume-title":"On the method of bounded differences, Surveys in Combinatorics: Invited Papers at the 12th British Combinatorial Conference","author":"McDiarmid C. J. H.","year":"1989"},{"key":"e_1_2_1_22_2","unstructured":"H.El MaftouhiandW. Fernandezde la Vega personal communication 1993."},{"key":"e_1_2_1_23_2","unstructured":"D.Mitchell B.Selman andH.Levesque Hard and easy distributions of SAT problems Proc. 10th National Conference on Artificial Intelligence 1992 pp.459\u2013465."},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_25_2","volume-title":"Large Deviations for Performance Analysis","author":"Shwartz A.","year":"1994"},{"key":"e_1_2_1_26_2","unstructured":"A.Weiss personal communication 1993."}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240070105","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240070105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T05:38:04Z","timestamp":1698298684000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240070105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,8]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,8]]}},"alternative-id":["10.1002\/rsa.3240070105"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240070105","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,8]]}}}