{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T04:25:54Z","timestamp":1747196754093,"version":"3.40.5"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319135236"},{"type":"electronic","value":"9783319135243"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13524-3_28","type":"book-chapter","created":{"date-parts":[[2014,12,2]],"date-time":"2014-12-02T17:51:38Z","timestamp":1417542698000},"page":"332-341","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments"],"prefix":"10.1007","author":[{"given":"Patrick","family":"Traxler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,3]]},"reference":[{"key":"28_CR1","doi-asserted-by":"publisher","first-page":"159","DOI":"10.2307\/1970980","volume":"102","author":"W Beckner","year":"1975","unstructured":"Beckner, W.: Inequalities in Fourier analysis. Ann. Math. 102, 159\u2013182 (1975)","journal-title":"Ann. Math."},{"issue":"2","key":"28_CR2","doi-asserted-by":"publisher","first-page":"335","DOI":"10.5802\/aif.357","volume":"20","author":"A Bonami","year":"1970","unstructured":"Bonami, A.: \u00c9tude des coefficients des Fourier de fonctions de $$L\\mathit{^p(G})$$. Annales de l\u2019Institut Fourier 20(2), 335\u2013402 (1970)","journal-title":"Annales de l\u2019Institut Fourier"},{"issue":"3","key":"28_CR3","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1016\/j.jcss.2007.06.015","volume":"74","author":"C Calabro","year":"2008","unstructured":"Calabro, C., Impagliazzo, R., Kabanets, V., Paturi, R.: The complexity of unique $$k$$-SAT: an isolation lemma for $$k$$-CNFs. J. Comput. Syst. Sci. 74(3), 386\u2013393 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R. A duality between clause width and clause density for SAT. In: Proceedings of the 21st Annual IEEE Conference on Computational Complexity, pp. 252\u2013260 (2006)","DOI":"10.1109\/CCC.2006.6"},{"issue":"4","key":"28_CR5","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1007\/s00453-012-9648-0","volume":"65","author":"C Calabro","year":"2013","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: On the exact complexity of evaluating quantified k-CNF. Algorithmica 65(4), 817\u2013827 (2013)","journal-title":"Algorithmica"},{"issue":"1","key":"28_CR6","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","volume":"5","author":"B Chor","year":"1989","unstructured":"Chor, B., Goldreich, O.: On the power of two-point based sampling. J. Complex. 5(1), 96\u2013106 (1989)","journal-title":"J. Complex."},{"issue":"2","key":"28_CR7","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<209::AID-RSA6>3.0.CO;2-1","volume":"16","author":"C Cooper","year":"2000","unstructured":"Cooper, C.: On the rank of random matrices. Random Struct. Algorithms 16(2), 209\u2013232 (2000)","journal-title":"Random Struct. Algorithms"},{"key":"28_CR8","first-page":"6","volume":"1","author":"R de Wolf","year":"2008","unstructured":"de Wolf, R.: A brief introduction to Fourier analysis on the Boolean cube. Theory Comput. Libr. Grad. Surv. 1, 6 (2008)","journal-title":"Theory Comput. Libr. Grad. Surv."},{"key":"28_CR9","unstructured":"Ermon, S., Gomes, C.P., Sabharwal, A., Selman, B.: Taming the curse of dimensionality: discrete integration by hashing and optimization. In: Proceedings of the 30th International Conference on Machine Learning, pp. 334\u2013342 (2013)"},{"key":"28_CR10","unstructured":"Ermon, S., Gomes, C.P., Sabharwal, A., Selman, B.: Low-density parity constraints for hashing-based discrete integration. In: Proceedings of the 31th International Conference on Machine Learning, pp. 271\u2013279 (2014)"},{"issue":"5","key":"28_CR11","doi-asserted-by":"publisher","first-page":"1695","DOI":"10.1137\/070706550","volume":"38","author":"D Gavinsky","year":"2008","unstructured":"Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R., de Wolf, R.: Exponential separations for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput. 38(5), 1695\u20131708 (2008)","journal-title":"SIAM J. Comput."},{"key":"28_CR12","unstructured":"Gomes, C.P., Sabharwal, A., Selman, B.: Model counting: a new strategy for obtaining good bounds. In: Proceedings of the 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference (2006)"},{"key":"28_CR13","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 12\u201324 (1989)","DOI":"10.1145\/73007.73009"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R, Matthews, W., Paturi, R.: A satisfiability algorithm for AC0. In: Proceedings of the 23th ACM-SIAM Symposium on Discrete Algorithms, pp. 961\u2013972 (2012)","DOI":"10.1137\/1.9781611973099.77"},{"issue":"4","key":"28_CR15","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"28_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.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. 43, 169\u2013188 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"28_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04650-0","volume-title":"Extremal Combinatorics","author":"S Jukna","year":"2001","unstructured":"Jukna, S.: Extremal Combinatorics. Springer, Heidelberg (2001)"},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R.: Some topics in analysis of boolean functions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 569\u2013578 (2008)","DOI":"10.1145\/1374376.1374458"},{"issue":"4","key":"28_CR19","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1137\/0214060","volume":"14","author":"LJ Stockmeyer","year":"1985","unstructured":"Stockmeyer, L.J.: On approximation algorithms for #P. SIAM J. Comput. 14(4), 849\u2013861 (1985)","journal-title":"SIAM J. Comput."},{"key":"28_CR20","unstructured":"Thurley, M.: An approximation algorithm for #k-SAT. In: Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, pp. 78\u201387 (2012)"},{"issue":"1","key":"28_CR21","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"LG Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theor. Comput. Sci. 47(1), 85\u201393 (1986)","journal-title":"Theor. Comput. Sci."},{"issue":"2\u20133","key":"28_CR22","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2\u20133), 357\u2013365 (2005)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13524-3_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T22:34:32Z","timestamp":1747175672000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13524-3_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319135236","9783319135243"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13524-3_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"3 December 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}