{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T09:32:06Z","timestamp":1691659926258},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2018,12,26]],"date-time":"2018-12-26T00:00:00Z","timestamp":1545782400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,12,26]],"date-time":"2018-12-26T00:00:00Z","timestamp":1545782400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1527668"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ExCAPE:Expeditions in Computer Augmented Program Engineering"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NUS ODPRT","award":["R-252-000-685-133"]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s10601-018-9301-x","type":"journal-article","created":{"date-parts":[[2018,12,26]],"date-time":"2018-12-26T12:14:12Z","timestamp":1545826452000},"page":"211-233","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Not all FPRASs are equal: demystifying FPRASs for DNF-counting"],"prefix":"10.1007","volume":"24","author":[{"given":"Kuldeep S.","family":"Meel","sequence":"first","affiliation":[]},{"given":"Aditya A.","family":"Shrotri","sequence":"additional","affiliation":[]},{"given":"Moshe Y.","family":"Vardi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,12,26]]},"reference":[{"key":"9301_CR1","doi-asserted-by":"crossref","unstructured":"Due\u00f1as-Osorio, L., Meel, K.S., Paredes, R., Vardi, M.Y. (2017). Counting-based reliability estimation for power-transmission grids. In Proceedings of AAAI conference on artificial intelligence (AAAI).","DOI":"10.1609\/aaai.v31i1.11178"},{"key":"9301_CR2","unstructured":"Bacchus, F., Dalmao, S., Pitassi, T. (2003). Algorithms and complexity results for #SAT and Bayesian inference, In Proceedings of FOCS (pp. 340\u2013351) ISBN: 0-7695-2040-5. http:\/\/dl.acm.org\/citation.cfm?id=946243.946291 ."},{"key":"9301_CR3","unstructured":"Sang, T., Beame, P., Kautz, H. (2005). Performing Bayesian inference by weighted model counting. In Prof. of AAAI (pp. 475\u2013481)."},{"issue":"4","key":"9301_CR4","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/s00778-006-0004-3","volume":"16","author":"N Dalvi","year":"2007","unstructured":"Dalvi, N., & Suciu, D. (2007). Efficient query evaluation on probabilistic databases. The VLDB Journal, 16(4), 523\u2013544.","journal-title":"The VLDB Journal"},{"key":"9301_CR5","doi-asserted-by":"crossref","unstructured":"Biondi, F., Enescu, M., Heuser, A., Legay, A., Meel, K.S., Quilbeuf, J. (2018). Scalable approximation of quantitative information flow in programs. In Proceedings of VMCAI.","DOI":"10.1007\/978-3-319-73721-8_4"},{"key":"9301_CR6","doi-asserted-by":"crossref","unstructured":"Karger, D.R. (2001). A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM Review.","DOI":"10.1137\/S0036144501387141"},{"issue":"3","key":"9301_CR7","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G. (1979). The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3), 410\u2013421.","journal-title":"SIAM Journal on Computing"},{"key":"9301_CR8","doi-asserted-by":"crossref","unstructured":"Karp, R.M., & Luby, M. (1983). Monte Carlo algorithms for enumeration and reliability problems. In Proceedings of FOCS.","DOI":"10.1109\/SFCS.1983.35"},{"issue":"3","key":"9301_CR9","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","volume":"10","author":"RM Karp","year":"1989","unstructured":"Karp, R.M., Luby, M., Madras, N. (1989). Monte Carlo approximation algorithms for enumeration problems. Journal of Algorithms, 10(3), 429\u2013448.","journal-title":"Journal of Algorithms"},{"key":"9301_CR10","unstructured":"Vazirani, V.V. (2013). Approximation algorithms. Springer Science & Business Media."},{"issue":"5","key":"9301_CR11","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539797315306","volume":"29","author":"P Dagum","year":"2000","unstructured":"Dagum, P., Karp, R., Luby, M., Ross, S. (2000). An optimal algorithm for Monte Carlo estimation. SIAM Journal on Computing, 29(5), 1484\u20131496.","journal-title":"SIAM Journal on Computing"},{"key":"9301_CR12","unstructured":"Chakraborty, S., Meel, K.S., Vardi, M.Y. (2016). Algorithmic improvements in approximate counting for probabilistic inference: from linear to logarithmic SAT call. In Proceedings of IJCAI."},{"key":"9301_CR13","unstructured":"Meel, K.S., Shrotri, A.A., Vardi, M.Y. (2017). On hashing-based approaches to approximate DNF-counting. In Proceedings of FSTTCS."},{"key":"9301_CR14","unstructured":"Ermon, S., Gomes, C.P., Sabharwal, A., Selman, B. (2013). Taming the curse of dimensionality: discrete integration by hashing and optimization. In Proceedings of ICML (pp. 334\u2013342)."},{"key":"9301_CR15","unstructured":"Meel, K.S. (2018). Constrained counting and sampling: bridging the gap between theory and practice. arXiv: 1806.02239 ."},{"key":"9301_CR16","unstructured":"Carter, J.L., & Wegman, M.N. (1977). Universal classes of hash functions. In Proceedings of STOC (pp. 106\u2013112). ACM."},{"issue":"4","key":"9301_CR17","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/BF01940873","volume":"16","author":"M Luby","year":"1996","unstructured":"Luby, M., & Veli\u010dkovi\u0107, B. (1996). On deterministic approximation of DNF. Algorithmica, 16(4), 415\u2013433.","journal-title":"Algorithmica"},{"key":"9301_CR18","doi-asserted-by":"crossref","unstructured":"Trevisan, L. (2004). A note on approximate counting for k-DNF. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques (pp. 417\u2013425). Springer.","DOI":"10.1007\/978-3-540-27821-4_37"},{"key":"9301_CR19","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Meka, R., Reingold, O. (2013). DNF sparsification and a faster deterministic counting algorithm. Computational Complexity.","DOI":"10.1007\/s00037-013-0068-6"},{"key":"9301_CR20","doi-asserted-by":"crossref","unstructured":"Ajtai, M., & Wigderson, A. (1985). Deterministic simulation of probabilistic constant depth circuits. In Proceedings of FOCS (pp. 11\u201319). IEEE.","DOI":"10.1109\/SFCS.1985.19"},{"issue":"1","key":"9301_CR21","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF01375474","volume":"11","author":"N Nisan","year":"1991","unstructured":"Nisan, N. (1991). Pseudorandom bits for constant depth circuits. Combinatorica, 11(1), 63\u201370.","journal-title":"Combinatorica"},{"key":"9301_CR22","doi-asserted-by":"crossref","unstructured":"De, A., Etesami, O., Trevisan, L., Tulsiani, M. (2010). Improved pseudorandom generators for depth 2 circuits. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques (pp. 504\u2013517). Springer.","DOI":"10.1007\/978-3-642-15369-3_38"},{"key":"9301_CR23","doi-asserted-by":"crossref","unstructured":"Olteanu, D., Huang, J., Koch, C. (2010). Approximate confidence computation in probabilistic databases. In ICDE (pp. 145\u2013156). IEEE.","DOI":"10.1109\/ICDE.2010.5447826"},{"key":"9301_CR24","doi-asserted-by":"crossref","unstructured":"Fink, R., & Olteanu, D. (2011). On the optimal approximation of queries using tractable propositional languages. In Proceedings of ICDT. ACM.","DOI":"10.1145\/1938551.1938575"},{"issue":"1","key":"9301_CR25","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/2532641","volume":"39","author":"W Gatterbauer","year":"2014","unstructured":"Gatterbauer, W., & Suciu, D. (2014). Oblivious bounds on the probability of Boolean functions. ACM TODS, 39(1), 5.","journal-title":"ACM TODS"},{"key":"9301_CR26","doi-asserted-by":"crossref","unstructured":"Tao, Q., Scott, S., Vinodchandran, N.V., Osugi, T.T. (2004). SVM-based generalized multiple-instance learning via approximate box counting. In Proceedings of the twenty-first international conference on machine learning (p. 101). ACM.","DOI":"10.1145\/1015330.1015405"},{"key":"9301_CR27","unstructured":"Babai, L. (1979). Monte-Carlo algorithms in graph isomorphism testing. Universit\u00e9 tde Montr\u00e9al Technical Report. DMS, pp 79\u201310."},{"key":"9301_CR28","doi-asserted-by":"crossref","unstructured":"Motwani, R., & Raghavan, P. (2010). Randomized algorithms.","DOI":"10.1201\/9781584888239-c12"},{"key":"9301_CR29","unstructured":"Albrecht, M., & Bard, G. (2012). The M4RI Library \u2013 Version 20121224. http:\/\/m4ri.sagemath.org ."},{"key":"9301_CR30","doi-asserted-by":"crossref","unstructured":"Huang, J., Antova, L., Koch, C., Olteanu, D. (2009). MayBMS: a probabilistic database management system. In Proceedings of SIGMOD. ACM.","DOI":"10.1145\/1559845.1559984"},{"key":"9301_CR31","unstructured":"TPC Benchmark H. http:\/\/www.tpc.org\/ ."},{"key":"9301_CR32","unstructured":"Mitchell, D., Selman, B., Levesque, H. (1992). Hard and easy distributions of SAT problems. In Proceedings of AAAI (pp. 459\u2013465)."},{"key":"9301_CR33","first-page":"424","volume-title":"Lecture Notes in Computer Science","author":"Marc Thurley","year":"2006","unstructured":"Thurley, M. (2006). SharpSAT: counting models with advanced component caching and implicit BCP. In Proceedings of SAT (pp. 424\u2013429)."},{"key":"9301_CR34","first-page":"200","volume-title":"Lecture Notes in Computer Science","author":"Supratik Chakraborty","year":"2013","unstructured":"Chakraborty, S., Meel, K.S., Vardi, M.Y. (2013). A scalable approximate model counter. In Proceedings of CP (pp. 200\u2013216)."}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-018-9301-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-018-9301-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-018-9301-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,9]],"date-time":"2022-09-09T03:00:11Z","timestamp":1662692411000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-018-9301-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,26]]},"references-count":34,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["9301"],"URL":"http:\/\/dx.doi.org\/10.1007\/s10601-018-9301-x","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,26]]},"assertion":[{"value":"26 December 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}
