{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T17:07:40Z","timestamp":1774631260459,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384280","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1139-1152","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Online vector balancing and geometric discrepancy"],"prefix":"10.1145","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Netherlands \/ CWI, Netherlands"}]},{"given":"Haotian","family":"Jiang","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}]},{"given":"Sahil","family":"Singla","sequence":"additional","affiliation":[{"name":"Princeton University, USA \/ Institute for Advanced Study at Princeton, USA"}]},{"given":"Makrand","family":"Sinha","sequence":"additional","affiliation":[{"name":"CWI, Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Balancing vectors and Gaussian measures of ndimensional convex bodies. Random Struct. Algorithms, 12 ( 4 ): 351-360","author":"Banaszczyk Wojciech","year":"1998","unstructured":"[Ban98] Wojciech Banaszczyk . Balancing vectors and Gaussian measures of ndimensional convex bodies. Random Struct. Algorithms, 12 ( 4 ): 351-360 , 1998 . [Ban98] Wojciech Banaszczyk. Balancing vectors and Gaussian measures of ndimensional convex bodies. Random Struct. Algorithms, 12 ( 4 ): 351-360, 1998."},{"key":"e_1_3_2_1_2_1","unstructured":"[Ban10] Nikhil Bansal. Constructive Algorithms for Discrepancy Minimization.  [Ban10] Nikhil Bansal. Constructive Algorithms for Discrepancy Minimization."},{"key":"e_1_3_2_1_3_1","first-page":"3","volume-title":"Proceedings of FOCS 2010","author":"In","year":"2010","unstructured":"In Proceedings of FOCS 2010 , pages 3 - 10 , 2010 . In Proceedings of FOCS 2010, pages 3-10, 2010."},{"key":"e_1_3_2_1_4_1","volume-title":"On series of signed vectors and their rearrangements. Random Struct. Algorithms, 40 ( 3 ): 301-316","author":"Banaszczyk Wojciech","year":"2012","unstructured":"[Ban12] Wojciech Banaszczyk . On series of signed vectors and their rearrangements. Random Struct. Algorithms, 40 ( 3 ): 301-316 , 2012 . [Ban12] Wojciech Banaszczyk. On series of signed vectors and their rearrangements. Random Struct. Algorithms, 40 ( 3 ): 301-316, 2012."},{"key":"e_1_3_2_1_5_1","first-page":"115","volume":"26","author":"B\u00e1r\u00e1ny Imre","year":"1979","unstructured":"[B\u00e1r79] Imre B\u00e1r\u00e1ny . On a Class of Balancing Games . J. Comb . Theory , Ser. A , 26 ( 2 ): 115 - 126 , 1979 . [B\u00e1r79] Imre B\u00e1r\u00e1ny. On a Class of Balancing Games. J. Comb. Theory, Ser. A, 26 ( 2 ): 115-126, 1979.","journal-title":"Ser. A"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85221-6_1"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.89"},{"key":"e_1_3_2_1_8_1","first-page":"587","volume-title":"Shachar Lovett. The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues. In Proceedings of STOC 2018","author":"Bansal Nikhil","year":"2018","unstructured":"[BDGL18] Nikhil Bansal , Daniel Dadush , Shashwat Garg , and Shachar Lovett. The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues. In Proceedings of STOC 2018 , pages 587 - 597 , 2018 . [BDGL18] Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett. The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues. In Proceedings of STOC 2018, pages 587-597, 2018."},{"key":"e_1_3_2_1_9_1","volume-title":"On some combinatorial questions in finite-dimensional spaces. Linear Algebra and its Applications, 41 : 1-9","author":"B\u00e1r\u00e1ny Imre","year":"1981","unstructured":"[BG81] Imre B\u00e1r\u00e1ny and Victor S Grinberg . On some combinatorial questions in finite-dimensional spaces. Linear Algebra and its Applications, 41 : 1-9 , 1981 . [BG81] Imre B\u00e1r\u00e1ny and Victor S Grinberg. On some combinatorial questions in finite-dimensional spaces. Linear Algebra and its Applications, 41 : 1-9, 1981."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055490"},{"key":"e_1_3_2_1_11_1","volume-title":"Online vector balancing and geometric discrepancy. CoRR, abs\/","author":"Bansal Nikhil","year":"1912","unstructured":"[BJSS19] Nikhil Bansal , Haotian Jiang , Sahil Singla , and Makrand Sinha . Online vector balancing and geometric discrepancy. CoRR, abs\/ 1912 .03350, http:\/\/arxiv.org\/abs\/ 1912.03350, 2019. [BJSS19] Nikhil Bansal, Haotian Jiang, Sahil Singla, and Makrand Sinha. Online vector balancing and geometric discrepancy. CoRR, abs\/ 1912.03350, http:\/\/arxiv.org\/abs\/ 1912.03350, 2019."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219179"},{"key":"e_1_3_2_1_13_1","unstructured":"[BS19] Nikhil Bansal and Joel H. Spencer. On-Line Balancing of Random Inputs.  [BS19] Nikhil Bansal and Joel H. Spencer. On-Line Balancing of Random Inputs."},{"key":"e_1_3_2_1_14_1","volume-title":"abs\/","year":"1903","unstructured":"CoRR , abs\/ 1903 .06898, 2019. CoRR, abs\/ 1903.06898, 2019."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0253-0_1"},{"key":"e_1_3_2_1_17_1","volume-title":"The power of online thinning in reducing discrepancy. Probability Theory and Related Fields, 174 : 103\u00e2\u0102\u015e131","author":"Dwivedi Raaz","year":"2019","unstructured":"[DFGGR19] Raaz Dwivedi , Ohad N. Feldheim , Ori Gurel-Gurevich , and Aaditya Ramdas . The power of online thinning in reducing discrepancy. Probability Theory and Related Fields, 174 : 103\u00e2\u0102\u015e131 , 2019 . [DFGGR19] Raaz Dwivedi, Ohad N. Feldheim, Ori Gurel-Gurevich, and Aaditya Ramdas. The power of online thinning in reducing discrepancy. Probability Theory and Related Fields, 174 : 103\u00e2\u0102\u015e131, 2019."},{"key":"e_1_3_2_1_18_1","first-page":"1405","volume-title":"Proceedings of AAAI","author":"Dickerson John P.","year":"2014","unstructured":"[DGK+14] John P. Dickerson , Jonathan R. Goldman , Jeremy Karp , Ariel D. Procaccia , and Tuomas Sandholm . The computational rise and fall of fairness . In Proceedings of AAAI , pages 1405 - 1411 , 2014 . [DGK+14] John P. Dickerson, Jonathan R. Goldman, Jeremy Karp, Ariel D. Procaccia, and Tuomas Sandholm. The computational rise and fall of fairness. In Proceedings of AAAI, pages 1405-1411, 2014."},{"key":"e_1_3_2_1_19_1","first-page":"1","volume-title":"Nicole TomczakJaegermann. Balancing Vectors in Any Norm. In Proceedings of FOCS 2018","author":"Dadush Daniel","year":"2018","unstructured":"[DNTT18] Daniel Dadush , Aleksandar Nikolov , Kunal Talwar , and Nicole TomczakJaegermann. Balancing Vectors in Any Norm. In Proceedings of FOCS 2018 , pages 1 - 10 , 2018 . [DNTT18] Daniel Dadush, Aleksandar Nikolov, Kunal Talwar, and Nicole TomczakJaegermann. Balancing Vectors in Any Norm. In Proceedings of FOCS 2018, pages 1-10, 2018."},{"key":"e_1_3_2_1_20_1","volume-title":"Eficient algorithms for discrepancy minimization in convex sets. Random Struct. Algorithms, 53 ( 2 ): 289-307","author":"Eldan Ronen","year":"2018","unstructured":"[ES18] Ronen Eldan and Mohit Singh . Eficient algorithms for discrepancy minimization in convex sets. Random Struct. Algorithms, 53 ( 2 ): 289-307 , 2018 . [ES18] Ronen Eldan and Mohit Singh. Eficient algorithms for discrepancy minimization in convex sets. Random Struct. Algorithms, 53 ( 2 ): 289-307, 2018."},{"key":"e_1_3_2_1_21_1","volume-title":"Resource allocation and the public sector. Yale Econ Essays, 7 : 45-98","author":"Foley Duncan K","year":"1967","unstructured":"[Fol67] Duncan K Foley . Resource allocation and the public sector. Yale Econ Essays, 7 : 45-98 , 1967 . [Fol67] Duncan K Foley. Resource allocation and the public sector. Yale Econ Essays, 7 : 45-98, 1967."},{"key":"e_1_3_2_1_22_1","unstructured":"[Fra18] Cole Franks. A simplified disproof of Beck's three permutations conjecture and an application to root-mean-squared discrepancy.  [Fra18] Cole Franks. A simplified disproof of Beck's three permutations conjecture and an application to root-mean-squared discrepancy."},{"key":"e_1_3_2_1_23_1","volume-title":"1811.01102","year":"2018","unstructured":"arXiv : 1811.01102 , 2018 . arXiv: 1811.01102, 2018."},{"key":"e_1_3_2_1_24_1","volume-title":"On some vector balancing problems. Studia Mathematica, 122 ( 3 ): 225-234","author":"Giannopoulos Apostolos A","year":"1997","unstructured":"[Gia97] Apostolos A Giannopoulos . On some vector balancing problems. Studia Mathematica, 122 ( 3 ): 225-234 , 1997 . [Gia97] Apostolos A Giannopoulos. On some vector balancing problems. Studia Mathematica, 122 ( 3 ): 225-234, 1997."},{"key":"e_1_3_2_1_25_1","volume-title":"Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization. arXiv","author":"Jiang Haotian","year":"1910","unstructured":"[JKS19] Haotian Jiang , Janardhan Kulkarni , and Sahil Singla . Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization. arXiv : 1910 .01073, 2019. [JKS19] Haotian Jiang, Janardhan Kulkarni, and Sahil Singla. Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization. arXiv: 1910.01073, 2019."},{"key":"e_1_3_2_1_26_1","first-page":"1573","volume":"44","author":"Lovett Shachar","year":"2015","unstructured":"[LM15] Shachar Lovett and Raghu Meka . Constructive Discrepancy Minimization by Walking on the Edges . SIAM J. Comput. , 44 ( 5 ): 1573 - 1582 , 2015 . [LM15] Shachar Lovett and Raghu Meka. Constructive Discrepancy Minimization by Walking on the Edges. SIAM J. Comput., 44 ( 5 ): 1573-1582, 2015.","journal-title":"J. Comput."},{"key":"e_1_3_2_1_27_1","unstructured":"[LMMS04] Richard J. Lipton Evangelos Markakis Elchanan Mossel and Amin Saberi.  [LMMS04] Richard J. Lipton Evangelos Markakis Elchanan Mossel and Amin Saberi."},{"key":"e_1_3_2_1_28_1","first-page":"125","volume-title":"Proceedings of EC 2004","author":"On","year":"2004","unstructured":"On approximately fair allocations of indivisible goods . In Proceedings of EC 2004 , pages 125 - 131 , 2004 . On approximately fair allocations of indivisible goods. In Proceedings of EC 2004, pages 125-131, 2004."},{"key":"e_1_3_2_1_29_1","unstructured":"[LRR17] Avi Levy Harishchandra Ramadas and Thomas Rothvoss. Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method.  [LRR17] Avi Levy Harishchandra Ramadas and Thomas Rothvoss. Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method."},{"key":"e_1_3_2_1_30_1","first-page":"380","volume-title":"Proceedings of IPCO 2017","author":"In","year":"2017","unstructured":"In Proceedings of IPCO 2017 , pages 380 - 391 , 2017 . In Proceedings of IPCO 2017, pages 380-391, 2017."},{"key":"e_1_3_2_1_31_1","volume-title":"An economic view of prophet inequalities. SIGecom Exchanges, 16 ( 1 ): 24-47","author":"Lucier Brendan","year":"2017","unstructured":"[Luc17] Brendan Lucier . An economic view of prophet inequalities. SIGecom Exchanges, 16 ( 1 ): 24-47 , 2017 . [Luc17] Brendan Lucier. An economic view of prophet inequalities. SIGecom Exchanges, 16 ( 1 ): 24-47, 2017."},{"key":"e_1_3_2_1_32_1","volume-title":"Geometric discrepancy: An illustrated guide","author":"Matousek Jiri","unstructured":"[Mat09] Jiri Matousek . Geometric discrepancy: An illustrated guide , volume 18 . [Mat09] Jiri Matousek. Geometric discrepancy: An illustrated guide, volume 18."},{"key":"e_1_3_2_1_33_1","unstructured":"Springer Science & Business Media 2009.  Springer Science & Business Media 2009."},{"key":"e_1_3_2_1_34_1","first-page":"1","volume-title":"Proceedings of SoCG 2015","author":"Matou\u0161ek Ji\u0159\u00ed","year":"2015","unstructured":"[MN15] Ji\u0159\u00ed Matou\u0161ek and Aleksandar Nikolov . Combinatorial discrepancy for boxes via the \u03b32 norm . In Proceedings of SoCG 2015 , pages 1 - 15 , 2015 . [MN15] Ji\u0159\u00ed Matou\u0161ek and Aleksandar Nikolov. Combinatorial discrepancy for boxes via the \u03b32 norm. In Proceedings of SoCG 2015, pages 1-15, 2015."},{"key":"e_1_3_2_1_35_1","volume-title":"Factorization norms and hereditary discrepancy. CoRR, abs\/1408.1376","author":"Matou\u0161ek Ji\u0159\u00ed","year":"2014","unstructured":"[MNT14] Ji\u0159\u00ed Matou\u0161ek , Aleksandar Nikolov , and Kunal Talwar . Factorization norms and hereditary discrepancy. CoRR, abs\/1408.1376 , 2014 . [MNT14] Ji\u0159\u00ed Matou\u0161ek, Aleksandar Nikolov, and Kunal Talwar. Factorization norms and hereditary discrepancy. CoRR, abs\/1408.1376, 2014."},{"key":"e_1_3_2_1_36_1","volume-title":"Tighter bounds for the discrepancy of boxes and polytopes. CoRR, abs\/1701.05532","author":"Nikolov Aleksandar","year":"2017","unstructured":"[Nik17] Aleksandar Nikolov . Tighter bounds for the discrepancy of boxes and polytopes. CoRR, abs\/1701.05532 , 2017 . [Nik17] Aleksandar Nikolov. Tighter bounds for the discrepancy of boxes and polytopes. CoRR, abs\/1701.05532, 2017."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.84"},{"key":"e_1_3_2_1_38_1","first-page":"409","volume-title":"Inverse Theorems, and Applications","author":"Nguyen Hoi H.","year":"2013","unstructured":"[NV13] Hoi H. Nguyen and Van H. Vu . Small Ball Probability , Inverse Theorems, and Applications , pages 409 - 463 . Springer Berlin Heidelberg , 2013 . [NV13] Hoi H. Nguyen and Van H. Vu. Small Ball Probability, Inverse Theorems, and Applications, pages 409-463. Springer Berlin Heidelberg, 2013."},{"key":"e_1_3_2_1_39_1","first-page":"140","volume-title":"Thomas Rothvo\u00df. Constructive Discrepancy Minimization for Convex Sets. In Proceedings of FOCS 2014","year":"2014","unstructured":"[Rot14] Thomas Rothvo\u00df. Constructive Discrepancy Minimization for Convex Sets. In Proceedings of FOCS 2014 , pages 140 - 145 , 2014 . [Rot14] Thomas Rothvo\u00df. Constructive Discrepancy Minimization for Convex Sets. In Proceedings of FOCS 2014, pages 140-145, 2014."},{"key":"e_1_3_2_1_40_1","first-page":"68","volume":"23","author":"Spencer Joel","year":"1977","unstructured":"[Spe77] Joel Spencer . Balancing games. J. Comb . Theory , Ser. B , 23 ( 1 ): 68 - 74 , 1977 . [Spe77] Joel Spencer. Balancing games. J. Comb. Theory, Ser. B, 23 ( 1 ): 68-74, 1977.","journal-title":"Ser. B"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1985-0784009-0"},{"key":"e_1_3_2_1_42_1","volume-title":"Ten lectures on the probabilistic method","author":"Spencer Joel H.","unstructured":"[Spe87] Joel H. Spencer . Ten lectures on the probabilistic method , volume 52 . [Spe87] Joel H. Spencer. Ten lectures on the probabilistic method, volume 52."},{"key":"e_1_3_2_1_43_1","unstructured":"Society for Industrial and Applied Mathematics Philadelphia 1987.  Society for Industrial and Applied Mathematics Philadelphia 1987."},{"key":"e_1_3_2_1_44_1","volume-title":"Proceedings of SODA","author":"Spencer Joel H.","year":"1997","unstructured":"[SST97] Joel H. Spencer , Aravind Srinivasan , and Prasad Tetali . The discrepancy of permutation families . In Proceedings of SODA , 1997 . [SST97] Joel H. Spencer, Aravind Srinivasan, and Prasad Tetali. The discrepancy of permutation families. In Proceedings of SODA, 1997."},{"key":"e_1_3_2_1_45_1","unstructured":"[TV85] William Thomson and Hal Varian. Theories of justice based on symmetry.  [TV85] William Thomson and Hal Varian. Theories of justice based on symmetry."},{"key":"e_1_3_2_1_46_1","first-page":"126","author":"Social","year":"1985","unstructured":"Social goals and social organizations: essays in memory of Elisha Pazner , 126 , 1985 . Social goals and social organizations: essays in memory of Elisha Pazner, 126, 1985.","journal-title":"Elisha Pazner"},{"key":"e_1_3_2_1_47_1","volume-title":"An Introduction to Wavelet Analysis. Applied and Numerical Harmonic Analysis. Birkh\u00c3\u010fuser Basel, 1 edition, 1","author":"Walnut David","year":"2004","unstructured":"[Wal04] David Walnut . An Introduction to Wavelet Analysis. Applied and Numerical Harmonic Analysis. Birkh\u00c3\u010fuser Basel, 1 edition, 1 2004 . [Wal04] David Walnut. An Introduction to Wavelet Analysis. Applied and Numerical Harmonic Analysis. Birkh\u00c3\u010fuser Basel, 1 edition, 1 2004."},{"key":"e_1_3_2_1_48_1","volume-title":"Fairness-eficiency tradeofs in dynamic fair division. CoRR, abs\/","author":"Zeng David","year":"1907","unstructured":"[ZP19] David Zeng and Alexandros Psomas . Fairness-eficiency tradeofs in dynamic fair division. CoRR, abs\/ 1907 .11672, 2019. [ZP19] David Zeng and Alexandros Psomas. Fairness-eficiency tradeofs in dynamic fair division. CoRR, abs\/ 1907.11672, 2019."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384280","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":48,"alternative-id":["10.1145\/3357713.3384280","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384280","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}