{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:40Z","timestamp":1750220080630,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,12]],"date-time":"2022-06-12T00:00:00Z","timestamp":1654992000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2015\/21"],"award-info":[{"award-number":["2015\/21"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Israel Ministry of Science and Technology"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,17]]},"DOI":"10.1145\/3530800.3534538","type":"proceedings-article","created":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T22:27:18Z","timestamp":1653344838000},"page":"1-8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Worst-case analysis for interactive evaluation of Boolean provenance"],"prefix":"10.1145","author":[{"given":"Antoine","family":"Amarilli","sequence":"first","affiliation":[{"name":"Institut Polytechnique de Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yael","family":"Amsterdamer","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,12]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/551350"},{"key":"e_1_3_2_1_2_1","volume-title":"Evaluation of monotone DNF formulas. Algorithmica, 77(3)","author":"Allen S. R.","year":"2017","unstructured":"S. R. Allen , L. Hellerstein , D. Kletenik , and T. \u00dcnl\u00fcyurt . Evaluation of monotone DNF formulas. Algorithmica, 77(3) , 2017 . S. R. Allen, L. Hellerstein, D. Kletenik, and T. \u00dcnl\u00fcyurt. Evaluation of monotone DNF formulas. Algorithmica, 77(3), 2017."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2095686.2095693"},{"key":"e_1_3_2_1_4_1","volume-title":"TaPP'11","author":"Amsterdamer Y.","year":"2011","unstructured":"Y. Amsterdamer , D. Deutch , and V. Tannen . On the limitations of provenance for queries with difference . In TaPP'11 , 2011 . Y. Amsterdamer, D. Deutch, and V. Tannen. On the limitations of provenance for queries with difference. In TaPP'11, 2011."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989302"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00227"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737786"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4567-5_3"},{"issue":"8","key":"e_1_3_2_1_9_1","first-page":"677","article-title":"Graph-based algorithms for boolean function manipulation. Computers","volume":"100","author":"Bryant R. E.","year":"1986","unstructured":"R. E. Bryant . Graph-based algorithms for boolean function manipulation. Computers , IEEE Transactions on , 100 ( 8 ): 677 -- 691 , 1986 . R. E. Bryant. Graph-based algorithms for boolean function manipulation. Computers, IEEE Transactions on, 100(8):677--691, 1986.","journal-title":"IEEE Transactions on"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645504.656274"},{"key":"e_1_3_2_1_11_1","volume-title":"Provenance in databases: Why, how, and where. Foundations and Trends in Databases, 1(4)","author":"Cheney J.","year":"2009","unstructured":"J. Cheney , L. Chiticariu , and W. C. Tan . Provenance in databases: Why, how, and where. Foundations and Trends in Databases, 1(4) , 2009 . J. Cheney, L. Chiticariu, and W. C. Tan. Provenance in databases: Why, how, and where. Foundations and Trends in Databases, 1(4), 2009."},{"key":"e_1_3_2_1_12_1","volume-title":"Citeseer","author":"Chronaki C. E.","year":"1990","unstructured":"C. E. Chronaki . A survey of evasiveness: Lower bounds on the decision-tree complexity of boolean functions. Technical report , Citeseer , 1990 . C. E. Chronaki. A survey of evasiveness: Lower bounds on the decision-tree complexity of boolean functions. Technical report, Citeseer, 1990."},{"key":"e_1_3_2_1_13_1","volume-title":"ICML","author":"Cicalese F.","year":"2014","unstructured":"F. Cicalese , E. S. Laber , and A. M. Saettler . Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost . In ICML , 2014 . F. Cicalese, E. S. Laber, and A. M. Saettler. Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost. In ICML, 2014."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.107"},{"key":"e_1_3_2_1_16_1","volume-title":"ICDT","author":"Deutch D.","year":"2014","unstructured":"D. Deutch , T. Milo , S. Roy , and V. Tannen . Circuits for datalog provenance . In ICDT , 2014 . D. Deutch, T. Milo, S. Roy, and V. Tannen. Circuits for datalog provenance. In ICDT, 2014."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00182"},{"key":"e_1_3_2_1_18_1","volume-title":"ALT","author":"Fiat A.","year":"2004","unstructured":"A. Fiat and D. Pechyony . Decision trees: More theoretical justification for practical algorithms . In ALT , 2004 . A. Fiat and D. Pechyony. Decision trees: More theoretical justification for practical algorithms. In ALT, 2004."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30215-5_13"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938575"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989331"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.15"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516472"},{"key":"e_1_3_2_1_24_1","first-page":"42","article-title":"Adaptive submodularity: Theory and applications in active learning and stochastic optimization","author":"Golovin D.","year":"2011","unstructured":"D. Golovin and A. Krause . Adaptive submodularity: Theory and applications in active learning and stochastic optimization . JAIR , 42 , 2011 . D. Golovin and A. Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. JAIR, 42, 2011.","journal-title":"JAIR"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_3_2_1_26_1","volume-title":"Incomplete information in relational databases. JACM, 31(4)","author":"Imielinski T.","year":"1984","unstructured":"T. Imielinski and W. L. Jr . Incomplete information in relational databases. JACM, 31(4) , 1984 . T. Imielinski and W. L. Jr. Incomplete information in relational databases. JACM, 31(4), 1984."},{"key":"e_1_3_2_1_27_1","volume-title":"Knowledge compilation meets database theory: Compiling queries to decision diagrams. Theory Comput. Syst., 52(3)","author":"Jha A. K.","year":"2013","unstructured":"A. K. Jha and D. Suciu . Knowledge compilation meets database theory: Compiling queries to decision diagrams. Theory Comput. Syst., 52(3) , 2013 . A. K. Jha and D. Suciu. Knowledge compilation meets database theory: Compiling queries to decision diagrams. Theory Comput. Syst., 52(3), 2013."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.4"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060644"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807269"},{"key":"e_1_3_2_1_31_1","first-page":"57","article-title":"Reduction of average path length in binary decision diagrams by spectral methods","author":"Keren O.","year":"2008","unstructured":"O. Keren . Reduction of average path length in binary decision diagrams by spectral methods . IEEE TOCS , 57 , 2008 . O. Keren. Reduction of average path length in binary decision diagrams by spectral methods. IEEE TOCS, 57, 2008.","journal-title":"IEEE TOCS"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/647999.742925"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236226"},{"key":"e_1_3_2_1_34_1","volume-title":"CIDR","author":"Marcus A.","year":"2011","unstructured":"A. Marcus , E. Wu , D. Karger , S. Madden , and R. Miller . Crowdsourced databases: query processing with people . In CIDR , 2011 . A. Marcus, E. Wu, D. Karger, S. Madden, and R. Miller. Crowdsourced databases: query processing with people. In CIDR, 2011."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274607"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00109"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398421"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/1952376.1952377"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1938551.1938582"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/120888703"},{"key":"e_1_3_2_1_41_1","volume-title":"Read-once functions and query evaluation in probabilistic databases. PVLDB, 3(1)","author":"Sen P.","year":"2010","unstructured":"P. Sen , A. Deshpande , and L. Getoor . Read-once functions and query evaluation in probabilistic databases. PVLDB, 3(1) , 2010 . P. Sen, A. Deshpande, and L. Getoor. Read-once functions and query evaluation in probabilistic databases. PVLDB, 3(1), 2010."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3236253"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/2031527"},{"key":"e_1_3_2_1_44_1","volume-title":"Sequential testing of complex systems: a review. Discrete Applied Mathematics, 142(1--3)","author":"\u00dcnl\u00fcyurt T.","year":"2004","unstructured":"T. \u00dcnl\u00fcyurt . Sequential testing of complex systems: a review. Discrete Applied Mathematics, 142(1--3) , 2004 . T. \u00dcnl\u00fcyurt. Sequential testing of complex systems: a review. Discrete Applied Mathematics, 142(1--3), 2004."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781680833157"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217031"}],"event":{"name":"SIGMOD\/PODS '22: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Philadelphia Pennsylvania","acronym":"SIGMOD\/PODS '22"},"container-title":["Proceedings of the 14th International Workshop on the Theory and Practice of Provenance"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530800.3534538","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3530800.3534538","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:25Z","timestamp":1750183765000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530800.3534538"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,12]]},"references-count":46,"alternative-id":["10.1145\/3530800.3534538","10.1145\/3530800"],"URL":"https:\/\/doi.org\/10.1145\/3530800.3534538","relation":{},"subject":[],"published":{"date-parts":[[2022,6,12]]},"assertion":[{"value":"2022-06-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}