{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:18Z","timestamp":1759637658037,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["708935"],"award-info":[{"award-number":["708935"]}],"id":[{"id":"10.13039\/501100007601","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["337122"],"award-info":[{"award-number":["337122"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1388\/16"],"award-info":[{"award-number":["1388\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055476","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"1028-1041","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximate modularity revisited"],"prefix":"10.1145","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Israel \/ Microsoft Research, Israel"}]},{"given":"Michal","family":"Feldman","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel \/ Microsoft Research, Israel"}]},{"given":"Inbal","family":"Talgam-Cohen","sequence":"additional","affiliation":[{"name":"Hebrew University of Jerusalem, Israel"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993741"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"crossref","unstructured":"Eric Balkanski Aviad Rubinstein and Yaron Singer. 2016. The Limitations of Optimization from Samples. (2016).  Eric Balkanski Aviad Rubinstein and Yaron Singer. 2016. The Limitations of Optimization from Samples. (2016).","DOI":"10.1145\/3055399.3055406"},{"key":"e_1_3_2_2_3_1","unstructured":"Working paper.  Working paper."},{"key":"e_1_3_2_2_4_1","volume-title":"Proceedings of the 28th Conference on Learning Theory. 240\u2013265","author":"Belloni Alexandre","year":"2015","unstructured":"Alexandre Belloni , Tengyuan Liang , Hariharan Narayanan , and Alexander Rakhlin . 2015 . Escaping the local minima via simulated annealing: Optimization of approximately convex functions . In Proceedings of the 28th Conference on Learning Theory. 240\u2013265 . Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, and Alexander Rakhlin. 2015. Escaping the local minima via simulated annealing: Optimization of approximately convex functions. In Proceedings of the 28th Conference on Learning Theory. 240\u2013265."},{"key":"e_1_3_2_2_5_1","unstructured":"Dimitris Bertsimas and Aur\/\u2019elie Thiele. 2014.  Dimitris Bertsimas and Aur\/\u2019elie Thiele. 2014."},{"volume-title":"Modern Decision Making Under Uncertainty. INFORMS PubsOnline","author":"Data-Driven Optimization Robust","key":"e_1_3_2_2_6_1","unstructured":"Robust and Data-Driven Optimization : Modern Decision Making Under Uncertainty. INFORMS PubsOnline , Chapter 5, 95\u2013122. TutORials in Operations Research . Robust and Data-Driven Optimization: Modern Decision Making Under Uncertainty. INFORMS PubsOnline, Chapter 5, 95\u2013122. TutORials in Operations Research."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_2_2_8_1","unstructured":"Andriy V. Bondarenko Andriy Prymak and Danylo Radchenko. 2013.  Andriy V. Bondarenko Andriy Prymak and Danylo Radchenko. 2013."},{"key":"e_1_3_2_2_9_1","volume-title":"234\u00e2\u0102\u015e\u2013241","author":"Concentrators On","year":"2013","unstructured":"On Concentrators and Related Approximation Constants . J. Math . Anal. Appl. 402, 1 ( 2013 ), 234\u00e2\u0102\u015e\u2013241 . On Concentrators and Related Approximation Constants. J. Math. Anal. Appl. 402, 1 (2013), 234\u00e2\u0102\u015e\u2013241."},{"key":"e_1_3_2_2_10_1","unstructured":"Flavio Chierichetti Abhimanyu Das Anirban Dasgupta and Ravi Kumar. 2015.  Flavio Chierichetti Abhimanyu Das Anirban Dasgupta and Ravi Kumar. 2015."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.74"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680977"},{"key":"e_1_3_2_2_13_1","unstructured":"Uriel Feige Michal Feldman and Inbal Talgam-Cohen. 2016.  Uriel Feige Michal Feldman and Inbal Talgam-Cohen. 2016."},{"key":"e_1_3_2_2_14_1","unstructured":"Approximate Modularity Revisited. (2016).  Approximate Modularity Revisited. (2016)."},{"key":"e_1_3_2_2_15_1","unstructured":"Full version available from https:\/\/arxiv.org\/abs\/ 1612.02034.  Full version available from https:\/\/arxiv.org\/abs\/ 1612.02034."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422466"},{"key":"e_1_3_2_2_17_1","volume-title":"Mirrokni","author":"Goemans Michel X.","year":"2009","unstructured":"Michel X. Goemans , Nicholas J. A. Harvey , Satoru Iwata , and Vahab S . Mirrokni . 2009 . Approximating submodular functions everywhere. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. 535\u2013544. Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, and Vahab S. Mirrokni. 2009. Approximating submodular functions everywhere. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. 535\u2013544."},{"key":"e_1_3_2_2_18_1","unstructured":"Avinatan Hassidim and Yaron Singer. 2016.  Avinatan Hassidim and Yaron Singer. 2016."},{"key":"e_1_3_2_2_19_1","unstructured":"Submodular Optimization under Noise. (2016).  Submodular Optimization under Noise. (2016)."},{"key":"e_1_3_2_2_20_1","unstructured":"Working paper available from https:\/\/arxiv.org\/abs\/1601.03095.  Working paper available from https:\/\/arxiv.org\/abs\/1601.03095."},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.27.4.222"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"e_1_3_2_2_23_1","unstructured":"S. M. Jung. 2011.  S. M. Jung. 2011."},{"key":"e_1_3_2_2_24_1","unstructured":"Hyers\u00e2\u0102\u015eUlam\u00e2\u0102\u015eRassias Stability of Functional Equations in Nonlinear Analysis. Springer.  Hyers\u00e2\u0102\u015eUlam\u00e2\u0102\u015eRassias Stability of Functional Equations in Nonlinear Analysis. Springer."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1983-0701524-4"},{"key":"e_1_3_2_2_26_1","unstructured":"Andreas Krause and Volkan Cevher. 2010.  Andreas Krause and Volkan Cevher. 2010."},{"volume-title":"Proceedings of the 27th International Conference on Machine Learning. 567\u2013574","author":"Submodular","key":"e_1_3_2_2_27_1","unstructured":"Submodular dictionary selection for sparse representation . In Proceedings of the 27th International Conference on Machine Learning. 567\u2013574 . Submodular dictionary selection for sparse representation. In Proceedings of the 27th International Conference on Machine Learning. 567\u2013574."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1390681.1390689"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"e_1_3_2_2_30_1","volume-title":"Gross Substitutability: An Algorithmic Survey.","author":"Leme Renato Paes","year":"2014","unstructured":"Renato Paes Leme . 2014 . Gross Substitutability: An Algorithmic Survey. (2014). Renato Paes Leme. 2014. Gross Substitutability: An Algorithmic Survey. (2014)."},{"key":"e_1_3_2_2_31_1","unstructured":"Working paper.  Working paper."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.4064\/cm-54-1-163-164"},{"key":"e_1_3_2_2_33_1","unstructured":"Nicholas Pippenger. 1977.  Nicholas Pippenger. 1977."},{"key":"e_1_3_2_2_34_1","volume-title":"298\u2013304","author":"Comput SIAM J.","year":"1977","unstructured":"Superconcentrators. SIAM J. Comput . 6, 2 ( 1977 ), 298\u2013304 . Superconcentrators. SIAM J. Comput. 6, 2 (1977), 298\u2013304."},{"key":"e_1_3_2_2_35_1","unstructured":"Tim Roughgarden Inbal Talgam-Cohen and Jan Vondr\u00e1k. 2016.  Tim Roughgarden Inbal Talgam-Cohen and Jan Vondr\u00e1k. 2016."},{"key":"e_1_3_2_2_36_1","unstructured":"When Are Welfare Guarantees Robust? (2016).  When Are Welfare Guarantees Robust? (2016)."},{"key":"e_1_3_2_2_37_1","unstructured":"Working paper available from https:\/\/arxiv. org\/abs\/1608.02402.  Working paper available from https:\/\/arxiv. org\/abs\/1608.02402."},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1989"},{"key":"e_1_3_2_2_39_1","volume-title":"Proceedings of the 28th Annual Conference on Neural Information Processing Systems. 3204\u20133212","author":"Singer Yaron","year":"2015","unstructured":"Yaron Singer and Jan Vondr\u00e1k . 2015 . Information-theoretic Lower Bounds for Convex Optimization with Erroneous Oracles . In Proceedings of the 28th Annual Conference on Neural Information Processing Systems. 3204\u20133212 . Yaron Singer and Jan Vondr\u00e1k. 2015. Information-theoretic Lower Bounds for Convex Optimization with Erroneous Oracles. In Proceedings of the 28th Annual Conference on Neural Information Processing Systems. 3204\u20133212."}],"event":{"name":"STOC '17: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Montreal Canada","acronym":"STOC '17"},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055476","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055476","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:19Z","timestamp":1750217779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055476"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":39,"alternative-id":["10.1145\/3055399.3055476","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055476","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}