{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:22:06Z","timestamp":1787509326342,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":74,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"BSF grant","award":["2014389"],"award-info":[{"award-number":["2014389"]}]},{"name":"NSF CAREER","award":["CCF-1452961"],"award-info":[{"award-number":["CCF-1452961"]}]},{"name":"NSF grant","award":["CCF-1301976"],"award-info":[{"award-number":["CCF-1301976"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188752","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T16:15:46Z","timestamp":1529511346000},"page":"1138-1151","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["The adaptive complexity of maximizing a submodular function"],"prefix":"10.1145","author":[{"given":"Eric","family":"Balkanski","sequence":"first","affiliation":[{"name":"Harvard University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yaron","family":"Singer","sequence":"additional","affiliation":[{"name":"Harvard University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"COLT","author":"Agarwal Arpit","year":"2017"},{"key":"e_1_3_2_2_2_1","volume-title":"Maximizing sequencesubmodular functions and its application to online advertising. arXiv preprint arXiv:1009.4153","author":"Alaei Saeed","year":"2010"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.95"},{"key":"e_1_3_2_2_4_1","volume-title":"Sequential adaptive compressed sampling via huffman codes. arXiv preprint arXiv:0810.4916","author":"Aldroubi Akram","year":"2008"},{"key":"e_1_3_2_2_5_1","volume-title":"AAMAS","author":"Balcan Maria-Florina","year":"2015"},{"key":"e_1_3_2_2_6_1","volume-title":"COLT","author":"Balcan Maria-Florina","year":"2012"},{"key":"e_1_3_2_2_7_1","first-page":"1035","volume-title":"SODA","author":"Ashwinkumar Badanidiyuru BDF","year":"2012"},{"key":"e_1_3_2_2_8_1","first-page":"1244","volume-title":"ICML","author":"Barbosa Rafael","year":"2015"},{"key":"e_1_3_2_2_9_1","first-page":"654","volume-title":"FOCS","author":"da Ponte Barbosa Rafael"},{"key":"e_1_3_2_2_10_1","volume-title":"The non-adaptive query complexity of testing k-parities. arXiv preprint arXiv:1209.3849","author":"Buhrman Harry","year":"2012"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993741"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/227234.227246"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897642"},{"key":"e_1_3_2_2_14_1","first-page":"429","volume-title":"SODA","author":"Ashwinkumar Badanidiyuru BPR"},{"key":"e_1_3_2_2_15_1","first-page":"32","volume-title":"SPAA","author":"Blelloch Guy E"},{"key":"e_1_3_2_2_16_1","first-page":"26","volume-title":"SPAA","author":"Blelloch Guy E"},{"key":"e_1_3_2_2_17_1","first-page":"59","volume-title":"FOCS","author":"Berger Bonnie"},{"key":"e_1_3_2_2_18_1","unstructured":"STOC\u201918 June 25\u201329 2018 Los Angeles CA USA Eric Balkanski and Yaron Singer  STOC\u201918 June 25\u201329 2018 Los Angeles CA USA Eric Balkanski and Yaron Singer"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055406"},{"key":"e_1_3_2_2_20_1","volume-title":"Minimizing a submodular function from samples","author":"Balkanski Eric","year":"2017"},{"key":"e_1_3_2_2_21_1","first-page":"301","volume-title":"COLT","author":"Balkanski Eric","year":"2017"},{"key":"e_1_3_2_2_22_1","first-page":"90","volume-title":"SPAA","author":"Blelloch Guy E"},{"key":"e_1_3_2_2_23_1","volume-title":"Taming the complexity of protein folding. Current opinion in structural biology, 21(1):4\u201311","author":"Bowman Gregory R","year":"2011"},{"key":"e_1_3_2_2_24_1","volume-title":"An adaptivity hierarchy theorem for property testing. arXiv preprint arXiv:1702.05678","author":"Canonne Clement","year":"2017"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772715"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217049"},{"key":"e_1_3_2_2_27_1","volume-title":"Settling the query complexity of non-adaptive junta testing. arXiv preprint arXiv:1704.06314","author":"Xi Chen CST","year":"2017"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_2_2_31_1","first-page":"91","volume-title":"STOC","author":"Duris Pavol"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892563"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591815"},{"key":"e_1_3_2_2_34_1","first-page":"66","volume-title":"KDD","author":"Domingos Pedro"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087574"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.4208\/cicp.2009.09.060"},{"key":"e_1_3_2_2_37_1","first-page":"702","volume-title":"COLT","author":"Feldman Vitaly","year":"2014"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.32"},{"key":"e_1_3_2_2_40_1","first-page":"942","volume-title":"FOCS","author":"Feldman Vitaly"},{"key":"e_1_3_2_2_41_1","first-page":"345","volume-title":"COLT","author":"Golovin Daniel","year":"2010"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963192.1963217"},{"key":"e_1_3_2_2_43_1","first-page":"1555","volume-title":"SSC","author":"Haupt Jarvis D"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSP.2009.4786013"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741127"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.83"},{"key":"e_1_3_2_2_47_1","first-page":"1321","volume-title":"NIPS","author":"Jegelka Stefanie","year":"2013"},{"key":"e_1_3_2_2_48_1","first-page":"468","volume-title":"NIPS","author":"Jegelka Stefanie","year":"2011"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2007.914345"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2809814"},{"key":"e_1_3_2_2_52_1","first-page":"948","volume-title":"SODA","author":"Karloff Howard"},{"key":"e_1_3_2_2_53_1","first-page":"2889","volume-title":"NIPS","author":"Mirzasoleiman Baharan","year":"2015"},{"key":"e_1_3_2_2_54_1","first-page":"2057","volume-title":"NIPS","author":"Mirzasoleiman Baharan","year":"2013"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225093"},{"key":"e_1_3_2_2_56_1","first-page":"3360","volume-title":"ICASSP","author":"Malioutov Dmitry M"},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746624"},{"key":"e_1_3_2_2_58_1","first-page":"648","volume-title":"NIPS","author":"Nishihara Robert","year":"2014"},{"key":"e_1_3_2_2_59_1","first-page":"3194","volume-title":"NIPS","author":"Narasimhan Harikrishna","year":"2015"},{"key":"e_1_3_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103463"},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_3_2_2_62_1","first-page":"126","volume-title":"NIPS","author":"Xinghao Pan PJG","year":"2014"},{"key":"e_1_3_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90069-2"},{"key":"e_1_3_2_2_64_1","first-page":"70","volume-title":"KDD","author":"Richardson Matthew"},{"key":"e_1_3_2_2_65_1","volume-title":"ECCC","author":"Raskhodnikova Sofya","year":"2006"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793260763"},{"key":"e_1_3_2_2_67_1","first-page":"468","volume-title":"FOCS","author":"Seeman Lior"},{"key":"e_1_3_2_2_68_1","first-page":"2043","volume-title":"AAAI","author":"Singla Adish","year":"2016"},{"key":"e_1_3_2_2_69_1","first-page":"279","volume-title":"CCC","author":"Servedio Rocco A","year":"2015"},{"key":"e_1_3_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1990.10474975"},{"key":"e_1_3_2_2_71_1","first-page":"1421","volume-title":"NIPS","author":"Tschiatschek Sebastian","year":"2014"},{"key":"e_1_3_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204030"},{"key":"e_1_3_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_2_74_1","first-page":"1502","volume-title":"ICML","author":"Wei Kai","year":"2014"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA","acronym":"STOC '18","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188752","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188752","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:07:08Z","timestamp":1750198028000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188752"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":74,"alternative-id":["10.1145\/3188745.3188752","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188752","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}