{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T09:30:46Z","timestamp":1775899846859,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642141645","type":"print"},{"value":"9783642141652","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_19","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"213-225","source":"Crossref","is-referenced-by-count":65,"title":["Tight Thresholds for Cuckoo Hashing via XORSAT"],"prefix":"10.1007","author":[{"given":"Martin","family":"Dietzfelbinger","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Goerdt","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Mitzenmacher","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Montanari","sequence":"additional","affiliation":[]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Rink","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"19_CR1","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/S0097539795288490","volume":"29","author":"Y. Azar","year":"1999","unstructured":"Azar, Y., Broder, A., Karlin, A., Upfal, E.: Balanced allocations. SIAM J. Comput.\u00a029(1), 180\u2013200 (1999)","journal-title":"SIAM J. Comput."},{"key":"19_CR2","unstructured":"Batu, T., Berenbrink, P., Cooper, C.: Balanced allocations: Balls-into-bins revisited and chains-into-bins, CDAM Research Report Series. LSE-CDAM-2007-34"},{"key":"19_CR3","unstructured":"Cain, J.A., Sanders, P., Wormald, N.C.: The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation. In: Proc. 18th ACM-SIAM SODA, pp. 469\u2013476 (2007)"},{"issue":"3","key":"19_CR4","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1017\/S0963548397003040","volume":"6","author":"N.J. Calkin","year":"1997","unstructured":"Calkin, N.J.: Dependent sets of constant weight binary vectors. Combinatorics, Probability, and Computing\u00a06(3), 263\u2013271 (1997)","journal-title":"Combinatorics, Probability, and Computing"},{"issue":"4","key":"19_CR5","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1002\/rsa.20040","volume":"25","author":"C. Cooper","year":"2004","unstructured":"Cooper, C.: The size of the cores of a random graph with a given degree sequence. Random Structures and Algorithms\u00a025(4), 353\u2013375 (2004)","journal-title":"Random Structures and Algorithms"},{"issue":"2","key":"19_CR6","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1051\/ita:2003014","volume":"37","author":"N. Creignou","year":"2003","unstructured":"Creignou, N., Daud\u00e9, H.: Smooth and sharp thresholds for random k-XOR-CNF satisfiability. Theoretical Informatics and Applications\u00a037(2), 127\u2013147 (2003)","journal-title":"Theoretical Informatics and Applications"},{"issue":"8","key":"19_CR7","doi-asserted-by":"publisher","first-page":"2085","DOI":"10.1016\/j.disc.2008.04.025","volume":"309","author":"N. Creignou","year":"2009","unstructured":"Creignou, N., Daud\u00e9, H.: The SAT-UNSAT transition for random constraint satisfaction problems. Discrete Mathematics\u00a0309(8), 2085\u20132099 (2009)","journal-title":"Discrete Mathematics"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R., Rink, M.: Tight Thresholds for Cuckoo Hashing via XORSAT. CoRR, abs\/0912.0287 (2009)","DOI":"10.1007\/978-3-642-14165-2_19"},{"key":"19_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-540-70575-8_32","volume-title":"Automata, Languages and Programming","author":"M. Dietzfelbinger","year":"2008","unstructured":"Dietzfelbinger, M., Pagh, R.: Succinct data structures for retrieval and approximate membership. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 385\u2013396. Springer, Heidelberg (2008)"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Dubois, O., Mandler, J.: The 3-XORSAT threshold. In: Proc. 43rd FOCS, pp. 769\u2013778 (2002)","DOI":"10.1109\/SFCS.2002.1182002"},{"key":"19_CR11","unstructured":"Fernholz, D., Ramachandran, V.: The k-orientability thresholds for G n, p . In: Proc. 18th ACM-SIAM SODA, pp. 459\u2013468 (2007)"},{"issue":"2","key":"19_CR12","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s00224-004-1195-x","volume":"38","author":"D. Fotakis","year":"2005","unstructured":"Fotakis, D., Pagh, R., Sanders, P., Spirakis, P.: Space efficient hash tables with worst case constant access time. Theory Comput. Syst.\u00a038(2), 229\u2013248 (2005)","journal-title":"Theory Comput. Syst."},{"key":"19_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1007\/978-3-642-14165-2_30","volume-title":"ICALP","author":"N. Fountoulakis","year":"2010","unstructured":"Fountoulakis, N., Panagiotou, K.: Orientability of random hypergaphs and the power of multiple choices. In: Gavoille, C. (ed.) ICALP 2010, Part I. LNCS, vol.\u00a06198, pp. 348\u2013359. Springer, Heidelberg (2010)"},{"key":"19_CR14","unstructured":"Fountoulakis, N., Panagiotou, K.: Sharp load thresholds for cuckoo hashing. CoRR, abs\/0910.5147 (2009)"},{"key":"19_CR15","unstructured":"Frieze, A.M., Melsted, P.: Maximum matchings in random bipartite graphs and the space utilization of cuckoo hashtables. CoRR, abs\/0910.5535 (2009)"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Gao, P., Wormald, N.C.: Load balancing and orientability thresholds for random hypergraphs. In: 42nd ACM STOC (to appear, 2010)","DOI":"10.1145\/1806689.1806705"},{"issue":"4","key":"19_CR17","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J.E. Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An n 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput.\u00a02(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"19_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1007\/978-3-642-04128-0_60","volume-title":"Algorithms - ESA 2009","author":"E. Lehman","year":"2009","unstructured":"Lehman, E., Panigrahy, R.: 3.5-way cuckoo hashing for the price of 2-and-a-bit. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 671\u2013681. Springer, Heidelberg (2009)"},{"issue":"2","key":"19_CR19","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1109\/18.910575","volume":"47","author":"M. Luby","year":"2001","unstructured":"Luby, M., Mitzenmacher, M., Shokrollahi, M.A., Spielman, D.: Efficient erasure correcting codes. IEEE Transactions on Information Theory\u00a047(2), 569\u2013584 (2001)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"12","key":"19_CR20","doi-asserted-by":"publisher","first-page":"5277","DOI":"10.1109\/TIT.2008.2006466","volume":"54","author":"C. M\u00e9asson","year":"2008","unstructured":"M\u00e9asson, C., Montanari, A., Urbanke, R.: Maxwell construction: the hidden bridge between iterative and maximum a posteriori decoding. IEEE Transactions on Information Theory\u00a054(12), 5277\u20135307 (2008)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"3\/4","key":"19_CR21","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1023\/A:1022886412117","volume":"111","author":"M. M\u00e9zard","year":"2003","unstructured":"M\u00e9zard, M., Ricci-Tersenghi, F., Zecchina, R.: Two solutions to diluted p-spin models and XORSAT problems. J. Statist. Phys.\u00a0111(3\/4), 505\u2013533 (2003)","journal-title":"J. Statist. Phys."},{"key":"19_CR22","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001","volume-title":"Information, Physics, and Computation","author":"M. M\u00e9zard","year":"2009","unstructured":"M\u00e9zard, M., Montanari, A.: Information, Physics, and Computation. Oxford University Press, Oxford (2009)"},{"key":"19_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-04128-0_1","volume-title":"Algorithms - ESA 2009","author":"M. Mitzenmacher","year":"2009","unstructured":"Mitzenmacher, M.: Some open questions related to cuckoo hashing. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 1\u201310. Springer, Heidelberg (2009)"},{"issue":"1","key":"19_CR24","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1002\/rsa.20061","volume":"27","author":"M. Molloy","year":"2005","unstructured":"Molloy, M.: Cores in random hypergraphs and Boolean formulas. Random Structures and Algorithms\u00a027(1), 124\u2013135 (2005)","journal-title":"Random Structures and Algorithms"},{"issue":"2","key":"19_CR25","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R. Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms\u00a051(2), 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"key":"19_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/978-3-540-24618-3_8","volume-title":"SOFSEM 2004: Theory and Practice of Computer Science","author":"P. Sanders","year":"2004","unstructured":"Sanders, P.: Algorithms for scalable storage servers. In: Van Emde Boas, P., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2004. LNCS, vol.\u00a02932, pp. 82\u2013101. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:48:16Z","timestamp":1606186096000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}