{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T02:44:35Z","timestamp":1725763475429},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642450297"},{"type":"electronic","value":"9783642450303"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45030-3_14","type":"book-chapter","created":{"date-parts":[[2013,12,11]],"date-time":"2013-12-11T21:32:52Z","timestamp":1386797572000},"page":"141-151","source":"Crossref","is-referenced-by-count":0,"title":["Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs"],"prefix":"10.1007","author":[{"given":"Marc","family":"Lelarge","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hang","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Bayati, M., Gamarnik, D., Katz, D., Nair, C., Tetali, P.: Simple deterministic approximation algorithms for counting matchings. In: STOC, pp. 122\u2013127. ACM (2007)","DOI":"10.1145\/1250790.1250809"},{"issue":"3","key":"14_CR2","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1006\/game.1993.1023","volume":"5","author":"L.E. Blume","year":"1993","unstructured":"Blume, L.E.: The statistical mechanics of strategic interaction. Games Econom. Behav.\u00a05(3), 387\u2013424 (1993)","journal-title":"Games Econom. Behav."},{"issue":"1-2","key":"14_CR3","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s00440-012-0453-0","volume":"157","author":"C. Bordenave","year":"2013","unstructured":"Bordenave, C., Lelarge, M., Salez, J.: Matchings on infinite graphs. Probability Theory and Related Fields\u00a0157(1-2), 183\u2013208 (2013)","journal-title":"Probability Theory and Related Fields"},{"issue":"1","key":"14_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0020-0190(94)00171-T","volume":"53","author":"R. Canetti","year":"1995","unstructured":"Canetti, R., Even, G., Goldreich, O.: Lower bounds for sampling algorithms for estimating the average. Information Processing Letters\u00a053(1), 17\u201325 (1995)","journal-title":"Information Processing Letters"},{"issue":"6","key":"14_CR5","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1137\/S0097539702403244","volume":"34","author":"B. Chazelle","year":"2005","unstructured":"Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. SIAM Journal on computing\u00a034(6), 1370\u20131379 (2005)","journal-title":"SIAM Journal on computing"},{"key":"14_CR6","first-page":"23","volume":"89","author":"A. Czumaj","year":"2006","unstructured":"Czumaj, A., Sohler, C.: Sublinear-time algorithms. Bulletin of the EATCS\u00a089, 23\u201347 (2006)","journal-title":"Bulletin of the EATCS"},{"issue":"4","key":"14_CR7","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1137\/S0097539704447304","volume":"35","author":"U. Feige","year":"2006","unstructured":"Feige, U.: On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM Journal on Computing\u00a035(4), 964\u2013984 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"8","key":"14_CR8","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1016\/j.jcss.2010.05.002","volume":"76","author":"D. Gamarnik","year":"2010","unstructured":"Gamarnik, D., Katz, D.: A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix. Journal of Computer and System Sciences\u00a076(8), 879\u2013883 (2010)","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR9","unstructured":"Gamarnik, D., Katz, D.: Correlation decay and deterministic FPTAS for counting list-colorings of a graph. In: SODA, pp. 1245\u20131254. SIAM (2007)"},{"issue":"3","key":"14_CR10","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1002\/jgt.3190050310","volume":"5","author":"C.D. Godsil","year":"1981","unstructured":"Godsil, C.D.: Matchings and walks in graphs. J. Graph Theory\u00a05(3), 285\u2013297 (1981)","journal-title":"J. Graph Theory"},{"issue":"4","key":"14_CR11","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1002\/rsa.20203","volume":"32","author":"O. Goldreich","year":"2008","unstructured":"Goldreich, O., Ron, D.: Approximating average parameters of graphs. Random Structures and Algorithms\u00a032(4), 473\u2013493 (2008)","journal-title":"Random Structures and Algorithms"},{"issue":"3","key":"14_CR12","doi-asserted-by":"publisher","first-page":"1365","DOI":"10.1137\/100783066","volume":"25","author":"M. Gonen","year":"2011","unstructured":"Gonen, M., Ron, D., Shavitt, Y.: Counting stars and other small subgraphs in sublinear-time. SIAM Journal on Discrete Mathematics\u00a025(3), 1365\u20131411 (2011)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"14_CR13","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/BF01877590","volume":"25","author":"O.J. Heilmann","year":"1972","unstructured":"Heilmann, O.J., Lieb, E.H.: Theory of monomer-dimer systems. Comm. Math. Phys.\u00a025, 190\u2013232 (1972)","journal-title":"Comm. Math. Phys."},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Jerrum, M.: Counting, sampling and integrating: algorithms and complexity. Lectures in Mathematics ETH Z\u00fcrich, Birkh\u00e4user Verlag, Basel (2003)","DOI":"10.1007\/978-3-0348-8005-3"},{"issue":"4","key":"14_CR15","doi-asserted-by":"publisher","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 nonnegative entries. Journal of the ACM\u00a051(4), 671\u2013697 (2004)","journal-title":"Journal of the ACM"},{"issue":"2-3","key":"14_CR16","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M. Jerrum","year":"1986","unstructured":"Jerrum, M., Valiant, L., Vazirani, V.: Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci.\u00a043(2-3), 169\u2013188 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"Li, L., Lu, P., Yin, Y.: Approximate counting via correlation decay in spin systems. In: SODA, pp. 922\u2013940. SIAM (2012)","DOI":"10.1137\/1.9781611973099.74"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Li, L., Lu, P., Yin, Y.: Correlation decay up to uniqueness in spin systems. In: SODA, pp. 67\u201384. SIAM (2013)","DOI":"10.1137\/1.9781611973105.5"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching theory. AMS Chelsea Publishing, Providence (2009) corrected reprint of the 1986 original (MR0859549)","DOI":"10.1090\/chel\/367"},{"key":"14_CR20","series-title":"Oxford Graduate Texts","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 Graduate Texts. Oxford University Press, Oxford (2009)"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Nguyen, H., Onak, K.: Constant-time approximation algorithms via local improvements. In: FOCS, pp. 327\u2013336. IEEE (2008)","DOI":"10.1109\/FOCS.2008.81"},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Onak, K., Ron, D., Rosen, M., Rubinfeld, R.: A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In: SODA, pp. 1123\u20131131. SIAM (2012)","DOI":"10.1137\/1.9781611973099.88"},{"issue":"1-3","key":"14_CR23","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.tcs.2007.04.040","volume":"381","author":"M. Parnas","year":"2007","unstructured":"Parnas, M., Ron, D.: Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoret. Comput. Sci.\u00a0381(1-3), 183\u2013196 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR24","first-page":"1095","volume-title":"International Congress of Mathematicians","author":"R. Rubinfeld","year":"2006","unstructured":"Rubinfeld, R.: Sublinear time algorithms. In: International Congress of Mathematicians, vol.\u00a0III, pp. 1095\u20131110. Eur. Math. Soc., Z\u00fcrich (2006)"},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Sinclair, A.: Algorithms for random generation and counting. In: Progress in Theoretical Computer Science, Birkh\u00e4user Boston Inc., Boston (1993)","DOI":"10.1007\/978-1-4612-0323-0"},{"key":"14_CR26","doi-asserted-by":"crossref","unstructured":"Sinclair, A., Srivastava, P., Thurley, M.: Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. In: SODA, pp. 941\u2013953. SIAM (2012)","DOI":"10.1137\/1.9781611973099.75"},{"key":"14_CR27","doi-asserted-by":"crossref","unstructured":"Sinclair, A., Srivastava, P.: Lee-yang theorems and the complexity of computing averages. In: STOC, pp. 625\u2013634. ACM (2013)","DOI":"10.1145\/2488608.2488686"},{"issue":"2","key":"14_CR28","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"S.P. Vadhan","year":"2002","unstructured":"Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graphs. SIAM Journal on Computing\u00a031(2), 398\u2013427 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"14_CR29","doi-asserted-by":"crossref","unstructured":"Weitz, D.: Counting independent sets up to the tree threshold. In: STOC, pp. 140\u2013149. ACM (2006)","DOI":"10.1145\/1132516.1132538"},{"key":"14_CR30","doi-asserted-by":"crossref","unstructured":"Welsh, D.J.A.: Complexity: knots, colourings and counting. London Mathematical Society Lecture Note Series, vol.\u00a0186. Cambridge University Press (1993)","DOI":"10.1017\/CBO9780511752506"},{"key":"14_CR31","doi-asserted-by":"crossref","unstructured":"Yao, A.: Probabilistic computations: Toward a unified measure of complexity. In: FOCS, pp. 222\u2013227. IEEE (1977)","DOI":"10.1109\/SFCS.1977.24"},{"key":"14_CR32","doi-asserted-by":"crossref","unstructured":"Yoshida, Y., Yamamoto, M., Ito, H.: An improved constant-time approximation algorithm for maximum independent sets and maximum matchings. In: STOC, pp. 225\u2013234. ACM (2009)","DOI":"10.1145\/1536414.1536447"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45030-3_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T06:40:34Z","timestamp":1558766434000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45030-3_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450297","9783642450303"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45030-3_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}