{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T04:07:43Z","timestamp":1748664463638,"version":"3.41.0"},"publisher-location":"Cham","reference-count":67,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319240237"},{"type":"electronic","value":"9783319240244"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-24024-4_13","type":"book-chapter","created":{"date-parts":[[2015,9,4]],"date-time":"2015-09-04T12:00:10Z","timestamp":1441368010000},"page":"196-222","source":"Crossref","is-referenced-by-count":0,"title":["Random Instances of Problems in NP \u2013 Algorithms and Statistical Physics"],"prefix":"10.1007","author":[{"given":"Charilaos","family":"Efthymiou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,22]]},"reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Coja-Oghlan, A.: Algorithmic Barriers from Phase Transitions. In: Proceedings of 49th IEEE Symposium on Foundations of Computer Science, FOCS (2008)","DOI":"10.1109\/FOCS.2008.11"},{"issue":"3","key":"13_CR2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1002\/rsa.20323","volume":"38","author":"D Achlioptas","year":"2011","unstructured":"Achlioptas, D., Coja-Oghlan, A., Ricci-Tersenghi, F.: On the solution-space geometry of random constraint satisfaction problems. Random Struct. Algorithms 38(3), 251\u2013268 (2011)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"13_CR3","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7","volume":"14","author":"D Achlioptas","year":"1999","unstructured":"Achlioptas, D., Friedgut, E.: A sharp threshold for $$k$$ -colorability. Random Struct. Algorithms 14(1), 63\u201370 (1999)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"13_CR4","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/S0097539703434231","volume":"36","author":"D Achlioptas","year":"2006","unstructured":"Achlioptas, D., Moore, C.: Random $$k$$ -SAT: two moments suffice to cross a sharp threshold. SIAM J. Comput. 36(3), 740\u2013762 (2006)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"13_CR5","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.4007\/annals.2005.162.1335","volume":"162","author":"D Achlioptas","year":"2005","unstructured":"Achlioptas, D., Naor, A.: The two possible values of the chromatic number of a random graph. Ann. Math. 162(3), 1333\u20131349 (2005)","journal-title":"Ann. Math."},{"key":"13_CR6","first-page":"947","volume":"17","author":"D Achlioptas","year":"2004","unstructured":"Achlioptas, D., Peres, Y.: The threshold for random $$k$$ -SAT is $$2^k \\log 2 - O(k)$$ . J. AMS 17, 947\u2013973 (2004)","journal-title":"J. AMS"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Alon, N., Krivelevich, M., Sudakov, B.: Finding a large hidden clique in a random graph. In: Proceedings of 9th ACM-SIAM Symposium on Discrete Algorithms, SODA 1998 (1998)","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.3.CO;2-K"},{"key":"13_CR8","unstructured":"Bapst, V., Coja-Oghlan, A., Hetterich, S., Rassmann, F., Vilenchik, D.: The condensation phase transition in random graph coloring. In: proceedings of APPROX-RANDOM 2014, pp. 449\u2013464 (2014)"},{"key":"13_CR9","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1214\/aop\/1176988728","volume":"22","author":"J Berg van den","year":"1994","unstructured":"van den Berg, J., Maes, C.: Disagreement percolation in the study of Markov fields. Ann. Probab. 22, 749\u2013763 (1994)","journal-title":"Ann. Probab."},{"key":"13_CR10","unstructured":"Bhatnagar, N., Sly, A., Tetali, P.: Decay of Correlations for the Hardcore Model on the $$d$$ -regular Random Graph. http:\/\/arxiv.org\/abs\/1405.6160"},{"key":"13_CR11","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/rsa.20057","volume":"27","author":"A Braunstein","year":"2004","unstructured":"Braunstein, A., M\u00e9zard, A., Zecchina, R.: Survey propagation: an algorithm for satisfiability. Random Struct. Algorithms 27, 201\u2013226 (2004)","journal-title":"Random Struct. Algorithms"},{"key":"13_CR12","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1002\/rsa.20006","volume":"24","author":"G Brightwell","year":"2004","unstructured":"Brightwell, G., Winkler, P.: A second threshold for the hard-core model on a Bethe lattice. Random Struct. Algorithms 24, 303\u2013314 (2004)","journal-title":"Random Struct. Algorithms"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Bubley, R., Dyer, M.: Path coupling: a technique for proving rapid mixing in markov chains. In: proceedings of 38th FOCS, pp 223\u2013231 (1997)","DOI":"10.1109\/SFCS.1997.646111"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A.: A Better Algorithm for Random $$k$$ -SAT. In: proceedings of ICALP (1) 2009: 292\u2013303. SIAM J. Comput. 39(7) 2823\u20132864 (2010)","DOI":"10.1137\/09076516X"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A.: The asymptotic $$k$$ -SAT threshold. In: proceedings of STOC 2014: 804\u2013813 (2014)","DOI":"10.1145\/2591796.2591822"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Efthymiou, C.: On independent sets in Random Graphs. In: Proceedings of 22nd ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp 136\u2013144 (2011)","DOI":"10.1137\/1.9781611973082.12"},{"key":"13_CR17","unstructured":"Coja-Oghlan, A., Efthymiou, C., Hetterich, S.: On the chromatic number of random regular graphs. http:\/\/arxiv.org\/abs\/1308.4287"},{"key":"13_CR18","unstructured":"Coja-Oghlan, A., Efthymiou, C., Jaafari, N.: Local convergence of random graph colorings. http:\/\/arxiv.org\/abs\/1501.06301"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Panagiotou, K.: Going after the k-SAT threshold. In: procedings of STOC 2013: 705\u2013714 (2013)","DOI":"10.1145\/2488608.2488698"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Panagiotou, K.: Catching the k-NAESAT threshold. In: proceedings of STOC 2012: 899\u2013908 (2012)","DOI":"10.1145\/2213977.2214058"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Vilenchik, D.: Chasing the k-colorability threshold. In: Proceedings of 54th IEEE Symposium on Foundations of Computer Science, FOCS 2013, pp 380\u2013389 (2013)","DOI":"10.1109\/FOCS.2013.48"},{"key":"13_CR22","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V., Reed, B.: Mick gets some (the odds are on his side). In: Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pp. 620\u2013627 (1992)","DOI":"10.1109\/SFCS.1992.267789"},{"key":"13_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1007\/978-3-642-22935-0_40","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"V Dani","year":"2011","unstructured":"Dani, V., Moore, C.: Independent sets in random graphs from the weighted second moment method. In: Goldberg, L.A., Jansen, K., Ravi, R., Rolim, J.D.P. (eds.) RANDOM 2011 and APPROX 2011. LNCS, vol. 6845, pp. 472\u2013482. Springer, Heidelberg (2011)"},{"key":"13_CR24","unstructured":"Ding, J., Sly, A., Sun, N.: Maximum independent sets on random regular graphs. http:\/\/arxiv.org\/abs\/1310.4787"},{"key":"13_CR25","doi-asserted-by":"crossref","unstructured":"Ding, J., Sly, A., Sun, N.: Satisfiability threshold for random regular NAE-SAT. In: proceendings of STOC 2014: 814\u2013822 (2014)","DOI":"10.1145\/2591796.2591862"},{"key":"13_CR26","doi-asserted-by":"crossref","unstructured":"Ding, J., Sly, A., Sun, N.: Proof of the satisfiability conjecture for large $$k$$ . To appear in STOC 2015 (2015)","DOI":"10.1145\/2746539.2746619"},{"key":"13_CR27","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1002\/rsa.20129","volume":"29","author":"M Dyer","year":"2006","unstructured":"Dyer, M., Flaxman, A., Frieze, A.M., Vigoda, E.: Random colouring sparse random graphs with fewer colours than the maximum degree. Random Struct. Algorithms 29, 450\u2013465 (2006)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"13_CR28","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1016\/0196-6774(89)90001-1","volume":"10","author":"ME Dyer","year":"1989","unstructured":"Dyer, M.E., Frieze, A.M.: The solution of some random np-hard problems in polynomial expected time. J. Algorithms 10(4), 451\u2013489 (1989)","journal-title":"J. Algorithms"},{"key":"13_CR29","doi-asserted-by":"crossref","unstructured":"Dyer, M., Frieze, A.M., Hayes, A., Vigoda, E.: Randomly colouring constant degree graphs. In proceedings of 45th FOCS, pp 582\u2013589 (2004)","DOI":"10.1109\/FOCS.2004.57"},{"key":"13_CR30","doi-asserted-by":"crossref","unstructured":"Efthymiou, C.: A simple algorithm for random colouring $$G(n, d\/n)$$ using $$(2 + \\epsilon )d$$ colours. In: Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 (2012)","DOI":"10.1137\/1.9781611973099.25"},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Efthymiou, C.: MCMC sampling colourings and independent sets of G(n, d\/n) near the uniqueness threshold. In: proceedings of Symposium on Discrete Algorithms, SODA (2014)","DOI":"10.1137\/1.9781611973402.22"},{"key":"13_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/978-3-662-44777-2_31","volume-title":"Algorithms - ESA 2014","author":"C Efthymiou","year":"2014","unstructured":"Efthymiou, C.: Switching colouring of G(n,d\/n) for sampling up to gibbs uniqueness threshold. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 371\u2013381. Springer, Heidelberg (2014)"},{"key":"13_CR33","unstructured":"Efthymiou, C.: Reconstruction\/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees. CoRR abs\/1406.3617 (2014)"},{"key":"13_CR34","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1023\/A:1026501619075","volume":"40","author":"WT Freeman","year":"2000","unstructured":"Freeman, W.T., Paztor, E.C., Carmichael, O.T.: Learning low-level vision. Int. J. Comput. Vis. 40, 25\u201347 (2000)","journal-title":"Int. J. Comput. Vis."},{"key":"13_CR35","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E Friedgut","year":"1999","unstructured":"Friedgut, E.: Necessary and sufficient conditions for sharp thresholds of graph properties, and the k-SAT problem. J. Amer. Math. Soc. 12, 1017\u20131054 (1999)","journal-title":"J. Amer. Math. Soc."},{"issue":"183","key":"13_CR36","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0012-365X(90)90149-C","volume":"81","author":"AM Frieze","year":"1990","unstructured":"Frieze, A.M.: On the independence number of random graphs. Discrete Math. 81(183), 171\u2013175 (1990)","journal-title":"Discrete Math."},{"issue":"1","key":"13_CR37","first-page":"121","volume":"8","author":"AM Frieze","year":"2006","unstructured":"Frieze, A.M., Vera, J.: On randomly colouring locally sparse graphs. Discrete Math. & Theor. Comput. Sci. 8(1), 121\u2013128 (2006)","journal-title":"Discrete Math. & Theor. Comput. Sci."},{"key":"13_CR38","doi-asserted-by":"crossref","unstructured":"Georgii, H.O.: Gibbs Measures and Phase Transitions, de Gruyter Stud. Math. 9, de Gruyter, Berlin (1988)","DOI":"10.1515\/9783110850147"},{"issue":"2","key":"13_CR39","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1137\/S0097539704445470","volume":"35","author":"LA Goldberg","year":"2005","unstructured":"Goldberg, L.A., Martin, R.A., Paterson, M.: Strong spatial mixing with fewer colors for lattice graphs. SIAM J. Comput. 35(2), 486\u2013517 (2005)","journal-title":"SIAM J. Comput."},{"issue":"02","key":"13_CR40","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1017\/S0305004100051124","volume":"77","author":"GR Grimmett","year":"1975","unstructured":"Grimmett, G.R., McDiarmid, C.J.H.: On colouring random graphs. Math. Proc. Camb. Phil. Soc. 77(02), 313\u2013332 (1975)","journal-title":"Math. Proc. Camb. Phil. Soc."},{"key":"13_CR41","doi-asserted-by":"crossref","unstructured":"Hayes, T., Vera, J., Vigoda, E.: Randomly coloring planar graphs with fewer colors than the maximum degree. In: proceedings of 39th STOC, pp 450\u2013458 (2007)","DOI":"10.1145\/1250790.1250857"},{"issue":"6","key":"13_CR42","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M Held","year":"1970","unstructured":"Held, M., Karp, R.M.: The traveling-salesman problem and minimum spanning trees. Oper. Res. 18(6), 1138\u20131162 (1970)","journal-title":"Oper. Res."},{"key":"13_CR43","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1002\/rsa.3240030402","volume":"3","author":"MR Jerrum","year":"1992","unstructured":"Jerrum, M.R.: Large cliques elude the Metropolis process. Random Struct. Algorithms 3, 347\u2013359 (1992)","journal-title":"Random Struct. Algorithms"},{"key":"13_CR44","unstructured":"Jerrum, M.R., Sinclair, A.: The Markov chain Monte Carlo method: an approach to approximate counting and integration. In: Approximation Algorithms for NP-hard Problems, (Dorit Hochbaum, ed.), PWS (1996)"},{"issue":"4","key":"13_CR45","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1145\/1008731.1008738","volume":"51","author":"M Jerrum","year":"2004","unstructured":"Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. J. ACM 51(4), 671\u2013697 (2004)","journal-title":"J. ACM"},{"key":"13_CR46","doi-asserted-by":"crossref","unstructured":"Karp, R., Sipser, M.: Maximum matchings in sparse random graphs. In: proceedings of FOCS 1981, pp. 364 375 (1981)","DOI":"10.1109\/SFCS.1981.21"},{"issue":"3","key":"13_CR47","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1214\/aoap\/1177005872","volume":"1","author":"FP Kelly","year":"1991","unstructured":"Kelly, F.P.: Loss networks. Ann. Appl. Probab. 1(3), 319\u2013378 (1991)","journal-title":"Ann. Appl. Probab."},{"key":"13_CR48","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C., Vecchi, M.: Optimisation by simulated annealing. Science 220, 671\u2013680 (1983)","journal-title":"Science"},{"issue":"3","key":"13_CR49","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U","volume":"12","author":"LM Kirousis","year":"1998","unstructured":"Kirousis, L.M., Kranakis, E., Krizanc, D., Stamatiou, Y.C.: Approximating the unsatisfiability threshold of random formulas. Random Struct. Algor. 12(3), 253\u2013269 (1998)","journal-title":"Random Struct. Algor."},{"key":"13_CR50","doi-asserted-by":"crossref","first-page":"10318","DOI":"10.1073\/pnas.0703685104","volume":"104","author":"F Krzakala","year":"2007","unstructured":"Krzakala, F., Montanari, A., Ricci-Tersenghi, F., Semerjianc, G., Zdeborova, L.: Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Natl. Acad. Sci. 104, 10318\u201310323 (2007)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"13_CR51","doi-asserted-by":"crossref","first-page":"498519","DOI":"10.1109\/18.910572","volume":"47","author":"F Kschischang","year":"2001","unstructured":"Kschischang, F., Frey, B., Loeliger, H.A.: Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theory 47, 498519 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"13_CR52","doi-asserted-by":"crossref","unstructured":"Levin, D., Peres, Y., Wilmer, E.: Markov Chains and Mixing Times. American Mathematical Society (2008)","DOI":"10.1090\/mbk\/058"},{"key":"13_CR53","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Vempala, S.: Simulated annealing in convex bodies and an $$O*(n^4)$$ volume algorithm. In: Proceedings of the 44th IEEE Foundations of Computer Science (FOCS 2003) (2003). Also in JCSS (FOCS 2003 special issue)","DOI":"10.1109\/SFCS.2003.1238237"},{"key":"13_CR54","doi-asserted-by":"crossref","unstructured":"Lucier, B., Molloy, M., Peres, Y.: The Glauber Dynamics for Colourings of Bounded Degree Trees. In: proceedings of RANDOM 2009, pp 631\u2013645 (2009)","DOI":"10.1007\/978-3-642-03685-9_47"},{"key":"13_CR55","unstructured":"Martinelli, F., Sinclair, A., Weitz, D.: Fast mixing for independent sets, colorings and other models on trees. In: proceedings of 15th SODA, pp 456\u2013465 (2004)"},{"key":"13_CR56","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N Metropolis","year":"1953","unstructured":"Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21, 1087\u20131092 (1953)","journal-title":"J. Chem. Phys."},{"issue":"5582","key":"13_CR57","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1126\/science.1073287","volume":"297","author":"M M\u00e9zard","year":"2002","unstructured":"M\u00e9zard, M., Parisi, G., Zecchina, R.: Analytic and algorithmic solution of random satisfiability problems. Science 297(5582), 812\u2013815 (2002)","journal-title":"Science"},{"key":"13_CR58","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/S0097539702401786","volume":"33","author":"M Molloy","year":"2004","unstructured":"Molloy, M.: The Glauber dynamics on the colourings of a graph with large girth and maximum degree. SIAM J. Comput. 33, 721\u2013737 (2004)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"13_CR59","doi-asserted-by":"crossref","first-page":"771","DOI":"10.1137\/090755862","volume":"25","author":"A Montanari","year":"2011","unstructured":"Montanari, A., Restrepo, R., Tetali, P.: Reconstruction and clustering in random constraint satisfaction problems. SIAM J. Discrete Math. 25(2), 771\u2013808 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"13_CR60","unstructured":"Montanari, A., Shah, D.: Counting good truth assignments of random $$k$$ -SAT formulae. In: proceedings of the 18th Annual ACM-SIAM, SODA 2007, pp 1255\u20131264 (2007)"},{"key":"13_CR61","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00440-010-0286-7","volume":"148","author":"E Mossel","year":"2010","unstructured":"Mossel, E., Sly, A.: Gibbs rapidly samples colorings of $$G_{n, d\/n}$$ . J. Probab. Theory Relat. fields 148, 1\u20132 (2010)","journal-title":"J. Probab. Theory Relat. fields"},{"key":"13_CR62","volume-title":"Probabilistic reasoning in intelligent systems: Networks of plausible inference","author":"J Pearl","year":"1988","unstructured":"Pearl, J.: Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan-Kaufmann, Palo Alto (1988)"},{"key":"13_CR63","doi-asserted-by":"crossref","unstructured":"Restrepo, R., Stefankovic, D., Vera, J.C., Vigoda, E., Yang, L.: Phase transition for glauber dynamics for independent sets on regular trees. In: proceedings SODA 2011, pp 945\u2013956 (2011)","DOI":"10.1137\/1.9781611973082.73"},{"key":"13_CR64","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1109\/18.910577","volume":"47","author":"T Richardson","year":"2001","unstructured":"Richardson, T., Urbanke, R.: The capacity of low-density parity check codes under message passing deconding. IEEE Trans. Inf. Theory 47, 599\u2013618 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"13_CR65","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for $$k$$ -SAT and constraint satisfaction problems. In: proceedings of Symposium on Foundations of Computer Science, FOCS 1999, pp 410\u2013419 (1999)","DOI":"10.1109\/SFFCS.1999.814612"},{"key":"13_CR66","doi-asserted-by":"crossref","unstructured":"Tetali, P., Vera, J.C., Vigoda, E., Yang, L.: Phase transition for the mixing time of the glauber dynamics for coloring regular trees. In: proceedings of SODA 2010, pp 1646\u20131656 (2010)","DOI":"10.1137\/1.9781611973075.134"},{"issue":"3","key":"13_CR67","doi-asserted-by":"crossref","first-page":"1555","DOI":"10.1063\/1.533196","volume":"41","author":"E Vigoda","year":"2000","unstructured":"Vigoda, E.: Improved bounds for sampling colorings. J. Math. Phys. 41(3), 1555\u20131569 (2000). A preliminary version appears in FOCS 1999","journal-title":"J. Math. Phys."}],"container-title":["Lecture Notes in Computer Science","Algorithms, Probability, Networks, and Games"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-24024-4_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T12:21:10Z","timestamp":1748607670000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-24024-4_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319240237","9783319240244"],"references-count":67,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-24024-4_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}