{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:51Z","timestamp":1759637691464},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_65","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"787-799","source":"Crossref","is-referenced-by-count":5,"title":["FPTAS for Weighted Fibonacci Gates and Its Applications"],"prefix":"10.1007","author":[{"given":"Pinyan","family":"Lu","sequence":"first","affiliation":[]},{"given":"Menghui","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Chihao","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"65_CR1","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1002\/rsa.20236","volume":"33","author":"A. Bandyopadhyay","year":"2008","unstructured":"Bandyopadhyay, A., Gamarnik, D.: Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models. Random Structures & Algorithms\u00a033(4), 452\u2013479 (2008)","journal-title":"Random Structures & Algorithms"},{"key":"65_CR2","doi-asserted-by":"crossref","unstructured":"Bayati, M., Gamarnik, D., Katz, D., Nair, C., Tetali, P.: Simple deterministic approximation algorithms for counting matchings. In: Proceedings of STOC, pp. 122\u2013127. ACM (2007)","DOI":"10.1145\/1250790.1250809"},{"key":"65_CR3","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Guo, H., Williams, T.: A complete dichotomy rises from the capture of vanishing signatures. In: Proceedings of STOC, pp. 635\u2013644. ACM (2013)","DOI":"10.1145\/2488608.2488687"},{"issue":"1","key":"65_CR4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.jcss.2010.06.005","volume":"77","author":"J.-Y. Cai","year":"2011","unstructured":"Cai, J.-Y., Lu, P.: Holographic algorithms: From art to science. Journal of Computer and System Sciences\u00a077(1), 41\u201361 (2011)","journal-title":"Journal of Computer and System Sciences"},{"key":"65_CR5","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holographic algorithms by Fibonacci gates and holographic reductions for hardness. In: Proceedings of FOCS, pp. 644\u2013653 (2008)","DOI":"10.1109\/FOCS.2008.34"},{"key":"65_CR6","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holant problems and counting CSP. In: Proceedings of STOC, pp. 715\u2013724 (2009)","DOI":"10.1145\/1536414.1536511"},{"key":"65_CR7","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holographic algorithms with matchgates capture precisely tractable planar #CSP. In: Proceedings of FOCS, pp. 427\u2013436. IEEE (2010)","DOI":"10.1109\/FOCS.2010.48"},{"issue":"4","key":"65_CR8","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1137\/100814585","volume":"40","author":"J.-Y. Cai","year":"2011","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Computational complexity of Holant problems. SIAM Journal on Computing\u00a040(4), 1101\u20131132 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"65_CR9","unstructured":"Galanis, A., Stefankovic, D., Vigoda, E.: Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. arXiv preprint arXiv:1203.2226 (2012)"},{"key":"65_CR10","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.jda.2010.10.002","volume":"12","author":"D. Gamarnik","year":"2012","unstructured":"Gamarnik, D., Katz, D.: Correlation decay and deterministic FPTAS for counting colorings of a graph. Journal of Discrete Algorithms\u00a012, 29\u201347 (2012)","journal-title":"Journal of Discrete Algorithms"},{"key":"65_CR11","doi-asserted-by":"crossref","unstructured":"Huang, S., Lu, P.: A dichotomy for real weighted Holant problems. In: Proceedings of CCC, pp. 96\u2013106. IEEE (2012)","DOI":"10.1109\/CCC.2012.16"},{"issue":"6","key":"65_CR12","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1137\/0218077","volume":"18","author":"M. Jerrum","year":"1989","unstructured":"Jerrum, M., Sinclair, A.: Approximating the permanent. SIAM Journal on Computing\u00a018(6), 1149\u20131178 (1989)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"65_CR13","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1137\/0222066","volume":"22","author":"M. Jerrum","year":"1993","unstructured":"Jerrum, M., Sinclair, A.: Polynomial-time approximation algorithms for the Ising model. SIAM Journal on Computing\u00a022(5), 1087\u20131116 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"65_CR14","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"},{"key":"65_CR15","doi-asserted-by":"crossref","unstructured":"Li, L., Lu, P., Yin, Y.: Approximate counting via correlation decay in spin systems. In: Proceedings of SODA, pp. 922\u2013940. SIAM (2012)","DOI":"10.1137\/1.9781611973099.74"},{"key":"65_CR16","doi-asserted-by":"crossref","unstructured":"Li, L., Lu, P., Yin, Y.: Correlation decay up to uniqueness in spin systems. In: Proceedings of SODA, pp. 67\u201384 (2013)","DOI":"10.1137\/1.9781611973105.5"},{"key":"65_CR17","doi-asserted-by":"crossref","unstructured":"Lin, C., Liu, J., Lu, P.: A simple FPTAS for counting edge covers. In: Proceedings of SODA, pp. 341\u2013348 (2014)","DOI":"10.1137\/1.9781611973402.25"},{"issue":"4","key":"65_CR18","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s004930070007","volume":"20","author":"N. Linial","year":"2000","unstructured":"Linial, N., Samorodnitsky, A., Wigderson, A.: A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica\u00a020(4), 545\u2013568 (2000)","journal-title":"Combinatorica"},{"key":"65_CR19","doi-asserted-by":"crossref","unstructured":"Lu, P., Wang, M., Zhang, C.: FPTAS for weighted Fibonacci gates and its applications. arXiv preprint arXiv:1402.4370 (2014)","DOI":"10.1007\/978-3-662-43948-7_65"},{"key":"65_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1007\/978-3-642-40328-6_44","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"P. Lu","year":"2013","unstructured":"Lu, P., Yin, Y.: Improved FPTAS for multi-spin systems. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol.\u00a08096, pp. 639\u2013654. Springer, Heidelberg (2013)"},{"key":"65_CR21","unstructured":"McQuillan, C.: Approximating Holant problems by winding. arXiv preprint arXiv:1301.2880 (2013)"},{"issue":"1-2","key":"65_CR22","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s00440-012-0421-8","volume":"156","author":"R. Restrepo","year":"2013","unstructured":"Restrepo, R., Shin, J., Tetali, P., Vigoda, E., Yang, L.: Improved mixing condition on the grid for counting and sampling independent sets. Probability Theory and Related Fields\u00a0156(1-2), 75\u201399 (2013)","journal-title":"Probability Theory and Related Fields"},{"key":"65_CR23","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: Proceedings of SODA, pp. 941\u2013953. SIAM (2012)","DOI":"10.1137\/1.9781611973099.75"},{"key":"65_CR24","doi-asserted-by":"crossref","unstructured":"Sly, A.: Computational transition at the uniqueness threshold. In: Proceedings of FOCS, pp. 287\u2013296. IEEE (2010)","DOI":"10.1109\/FOCS.2010.34"},{"key":"65_CR25","doi-asserted-by":"crossref","unstructured":"Sly, A., Sun, N.: The computational hardness of counting in two-spin models on d-regular graphs. In: Proceedings of FOCS, pp. 361\u2013369. IEEE (2012)","DOI":"10.1109\/FOCS.2012.56"},{"issue":"5","key":"65_CR26","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1137\/070682575","volume":"37","author":"L.G. Valiant","year":"2008","unstructured":"Valiant, L.G.: Holographic algorithms. SIAM Journal on Computing\u00a037(5), 1565\u20131594 (2008)","journal-title":"SIAM Journal on Computing"},{"key":"65_CR27","doi-asserted-by":"crossref","unstructured":"Weitz, D.: Counting independent sets up to the tree threshold. In: Proceedings of STOC, pp. 140\u2013149. ACM (2006)","DOI":"10.1145\/1132516.1132538"},{"key":"65_CR28","doi-asserted-by":"crossref","unstructured":"Yin, Y., Zhang, C.: Approximate counting via correlation decay on planar graphs. In: Proceedings of SODA, pp. 47\u201366. SIAM (2013)","DOI":"10.1137\/1.9781611973105.4"}],"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-662-43948-7_65","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:13:17Z","timestamp":1558923197000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_65","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}