{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,27]],"date-time":"2026-08-27T23:09:17Z","timestamp":1787872157751,"version":"build-2784847793"},"publisher-location":"New York, NY, USA","reference-count":42,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055490","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T16:27:45Z","timestamp":1497544065000},"page":"914-926","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Algorithmic discrepancy beyond partial coloring"],"prefix":"10.1145","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shashwat","family":"Garg","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90026-9"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199807)12:4%3C351::AID-RSA3%3E3.0.CO;2-S"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.7"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20373"},{"key":"e_1_3_2_2_5_1","volume-title":"Springer","author":"B\u00e1r\u00e1ny Imre","year":"2008","unstructured":"{B\u00e1r08} Imre B\u00e1r\u00e1ny . On the power of linear dependencies. In Building bridges, pages 31\u201345 . Springer , 2008 . {B\u00e1r08} Imre B\u00e1r\u00e1ny. On the power of linear dependencies. In Building bridges, pages 31\u201345. Springer, 2008."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.5"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.89"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579453"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579452"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90129-X"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0474-y"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-33461-5_31"},{"issue":"2","key":"e_1_3_2_2_13_1","first-page":"215","article-title":"On the discrepancy of 3 permutations. Random Structures &","volume":"1","author":"Bohus G\u00e9za","year":"1990","unstructured":"{Boh90} G\u00e9za Bohus . On the discrepancy of 3 permutations. Random Structures & Algorithms , 1 ( 2 ): 215 \u2013 220 , 1990 . {Boh90} G\u00e9za Bohus. On the discrepancy of 3 permutations. Random Structures & Algorithms, 1(2):215\u2013220, 1990.","journal-title":"Algorithms"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/507108"},{"key":"e_1_3_2_2_15_1","volume-title":"Springer","author":"Chobanyan Sergej","year":"1994","unstructured":"{Cho94} Sergej Chobanyan . Convergence as of rearranged random series in Banach space and associated inequalities. In Probability in Banach Spaces, 9, pages 3\u201329 . Springer , 1994 . {Cho94} Sergej Chobanyan. Convergence as of rearranged random series in Banach space and associated inequalities. In Probability in Banach Spaces, 9, pages 3\u201329. Springer, 1994."},{"key":"e_1_3_2_2_16_1","volume-title":"A Panorama of Discrepancy Theory","author":"William Chen CST","year":"2014","unstructured":"{ CST + 14} William Chen , Anand Srivastav , Giancarlo Travaglini , A Panorama of Discrepancy Theory , volume 2107 . Springer , 2014 . {CST + 14} William Chen, Anand Srivastav, Giancarlo Travaglini, et al. A Panorama of Discrepancy Theory, volume 2107. Springer, 2014."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0384-4"},{"key":"e_1_3_2_2_18_1","volume-title":"APPROX\/RANDOM","volume":"60","author":"Dadush Daniel","year":"2016","unstructured":"{DGLN16} Daniel Dadush , Shashwat Garg , Shachar Lovett , and Aleksandar Nikolov . Towards a constructive version of banaszczyk\u2019s vector balancing theorem . In APPROX\/RANDOM , volume 60 , 2016 . {DGLN16} Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov. Towards a constructive version of banaszczyk\u2019s vector balancing theorem. In APPROX\/RANDOM, volume 60, 2016."},{"key":"e_1_3_2_2_19_1","volume-title":"Efficient algorithms for discrepancy minimization in convex sets. CoRR, abs\/1409.2913","author":"Eldan Ronen","year":"2014","unstructured":"{ES14} Ronen Eldan and Mohit Singh . Efficient algorithms for discrepancy minimization in convex sets. CoRR, abs\/1409.2913 , 2014 . {ES14} Ronen Eldan and Mohit Singh. Efficient algorithms for discrepancy minimization in convex sets. CoRR, abs\/1409.2913, 2014."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996452"},{"issue":"1","key":"e_1_3_2_2_21_1","first-page":"85","article-title":"Extremal properties of orthogonal parallelepipeds and their applications to the geometry of banach spaces. Sbornik","volume":"64","author":"Gluskin Efim Davydovich","year":"1989","unstructured":"{Glu89} Efim Davydovich Gluskin . Extremal properties of orthogonal parallelepipeds and their applications to the geometry of banach spaces. Sbornik : Mathematics , 64 ( 1 ): 85 \u2013 96 , 1989 . {Glu89} Efim Davydovich Gluskin. Extremal properties of orthogonal parallelepipeds and their applications to the geometry of banach spaces. Sbornik: Mathematics, 64(1):85\u201396, 1989.","journal-title":"Mathematics"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-22015-9","volume-title":"Approximation algorithms and semidefinite programming","author":"G\u00e4rtner Bernd","year":"2012","unstructured":"{GM12} Bernd G\u00e4rtner and Jiri Matousek . Approximation algorithms and semidefinite programming . Springer Science & amp; Business Media, 2012 . {GM12} Bernd G\u00e4rtner and Jiri Matousek. Approximation algorithms and semidefinite programming. Springer Science & Business Media, 2012."},{"key":"e_1_3_2_2_23_1","volume-title":"Value of the steinitz constant. Funktsional. Anal. i Prilozhen., 14(2):56\u201357","author":"Grinberg V. S.","year":"1980","unstructured":"{GS80} V. S. Grinberg and S. V. Sevastjanov . Value of the steinitz constant. Funktsional. Anal. i Prilozhen., 14(2):56\u201357 , 1980 . {GS80} V. S. Grinberg and S. V. Sevastjanov. Value of the steinitz constant. Funktsional. Anal. i Prilozhen., 14(2):56\u201357, 1980."},{"key":"e_1_3_2_2_24_1","series-title":"Bibliography Series of Vectors and Riemann Sums","volume-title":"Halperin and Tsuyoshi Ando","author":"I.","year":"1989","unstructured":"{HA89} I. Halperin and Tsuyoshi Ando . Bibliography Series of Vectors and Riemann Sums . Hokkaido Univ. , Research Institute of Applied Electricity, 1989 . {HA89} I. Halperin and Tsuyoshi Ando. Bibliography Series of Vectors and Riemann Sums. Hokkaido Univ., Research Institute of Applied Electricity, 1989."},{"key":"e_1_3_2_2_25_1","first-page":"1182","volume-title":"COLT","author":"Harvey Nick","year":"2014","unstructured":"{HS14} Nick Harvey and Samira Samadi . Near-optimal herding . In COLT , pages 1165\u2013 1182 , 2014 . {HS14} Nick Harvey and Samira Samadi. Near-optimal herding. In COLT, pages 1165\u20131182, 2014."},{"key":"e_1_3_2_2_26_1","first-page":"273","volume-title":"APPROX\/RANDOM 2014","author":"Harvey Nicholas J. A.","year":"2014","unstructured":"{HSS14} Nicholas J. A. Harvey , Roy Schwartz , and Mohit Singh . Discrepancy without partial colorings . In APPROX\/RANDOM 2014 , pages 258\u2013 273 , 2014 . {HSS14} Nicholas J. A. Harvey, Roy Schwartz, and Mohit Singh. Discrepancy without partial colorings. In APPROX\/RANDOM 2014, pages 258\u2013273, 2014."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/120865240"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.23"},{"key":"e_1_3_2_2_29_1","volume-title":"Deterministic discrepancy minimization via the multiplicative weight update method. arXiv preprint arXiv:1611.08752","author":"Levy Avi","year":"2016","unstructured":"{LRR16} Avi Levy , Harishchandra Ramadas , and Thomas Rothvoss . Deterministic discrepancy minimization via the multiplicative weight update method. arXiv preprint arXiv:1611.08752 , 2016 . {LRR16} Avi Levy, Harishchandra Ramadas, and Thomas Rothvoss. Deterministic discrepancy minimization via the multiplicative weight update method. arXiv preprint arXiv:1611.08752, 2016."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2018773"},{"key":"e_1_3_2_2_31_1","volume-title":"On the discrepancy for boxes and polytopes","year":"1999","unstructured":"{Mat99} Jir? Matousek. On the discrepancy for boxes and polytopes , 1999 . {Mat99} Jir? Matousek. On the discrepancy for boxes and polytopes, 1999."},{"key":"e_1_3_2_2_32_1","volume-title":"Geometric discrepancy: An illustrated guide","author":"Matousek Jiri","year":"2009","unstructured":"{Mat09} Jiri Matousek . Geometric discrepancy: An illustrated guide . Springer Science , 2009 . {Mat09} Jiri Matousek. Geometric discrepancy: An illustrated guide. Springer Science, 2009."},{"key":"e_1_3_2_2_33_1","volume-title":"Factorization norms and hereditary discrepancy. arXiv preprint arXiv:1408.1376","author":"Matousek Jiri","year":"2014","unstructured":"{MNT14} Jiri Matousek , Aleksandar Nikolov , and Kunal Talwar . Factorization norms and hereditary discrepancy. arXiv preprint arXiv:1408.1376 , 2014 . {MNT14} Jiri Matousek, Aleksandar Nikolov, and Kunal Talwar. Factorization norms and hereditary discrepancy. arXiv preprint arXiv:1408.1376, 2014."},{"key":"e_1_3_2_2_35_1","volume-title":"Tighter bounds for the discrepancy of boxes and polytopes. arXiv preprint arXiv:1701.05532","author":"Nikolov Aleksandar","year":"2017","unstructured":"{Nik17} Aleksandar Nikolov . Tighter bounds for the discrepancy of boxes and polytopes. arXiv preprint arXiv:1701.05532 , 2017 . {Nik17} Aleksandar Nikolov. Tighter bounds for the discrepancy of boxes and polytopes. arXiv preprint arXiv:1701.05532, 2017."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488652"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.11"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.23"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.23"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90036-1"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1985-0784009-0"},{"key":"e_1_3_2_2_42_1","first-page":"701","volume-title":"SODA","author":"Srinivasan Aravind","year":"1997","unstructured":"{Sri97} Aravind Srinivasan . Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems . In SODA , pages 692\u2013 701 , 1997 . {Sri97} Aravind Srinivasan. Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems. In SODA, pages 692\u2013701, 1997."},{"key":"e_1_3_2_2_43_1","volume-title":"Bedingt konvergente reihen und konvexe systeme.(schlu\u00df.). Journal f\u00fcr die reine und angewandte Mathematik, 146:1\u201352","author":"Steinitz Ernst","year":"1916","unstructured":"{Ste16} Ernst Steinitz . Bedingt konvergente reihen und konvexe systeme.(schlu\u00df.). Journal f\u00fcr die reine und angewandte Mathematik, 146:1\u201352 , 1916 . {Ste16} Ernst Steinitz. Bedingt konvergente reihen und konvexe systeme.(schlu\u00df.). Journal f\u00fcr die reine und angewandte Mathematik, 146:1\u201352, 1916."}],"event":{"name":"STOC '17: Symposium on Theory of Computing","location":"Montreal Canada","acronym":"STOC '17","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3055490","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055490","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:36:19Z","timestamp":1750203379000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055490"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":42,"alternative-id":["10.1145\/3055399.3055490","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055490","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"}}]}}