{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T18:30:48Z","timestamp":1684261848581},"publisher-location":"New York, NY, USA","reference-count":100,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384284","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["An improved cutting plane method for convex optimization, convex-concave games, and its applications"],"prefix":"10.1145","author":[{"given":"Haotian","family":"Jiang","sequence":"first","affiliation":[{"name":"University of Washington, USA"}]},{"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Washington, USA \/ Microsoft Research, USA"}]},{"given":"Zhao","family":"Song","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study at Princeton, USA \/ Princeton University, USA"}]},{"given":"Sam Chiu-wai","family":"Wong","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907353"},{"key":"e_1_3_2_1_2_1","volume-title":"International Conference on Machine Learning (ICML). https:\/\/arxiv.org\/ pdf\/ 1804","author":"Avron Haim","year":"2017","unstructured":"[AKM+17] Haim Avron , Michael Kapralov , Cameron Musco , Christopher Musco , Ameya Velingker , and Amir Zandieh . Random Fourier features for kernel ridge regression: Approximation bounds and statistical guarantees . In International Conference on Machine Learning (ICML). https:\/\/arxiv.org\/ pdf\/ 1804 .09893.pdf, 2017 . [AKM+17] Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh. Random Fourier features for kernel ridge regression: Approximation bounds and statistical guarantees. In International Conference on Machine Learning (ICML). https:\/\/arxiv.org\/ pdf\/ 1804.09893.pdf, 2017."},{"key":"e_1_3_2_1_3_1","volume-title":"51st Annual ACM SIGACT Symposium on Theory of Computing (STOC). https:\/\/arxiv.","author":"Avron Haim","unstructured":"[AKM+19] Haim Avron , Michael Kapralov , Cameron Musco , Christopher Musco , Ameya Velingker , and Amir Zandieh . A universal sampling method for reconstructing signals with simple Fourier transforms . In 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC). https:\/\/arxiv. [AKM+19] Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh. A universal sampling method for reconstructing signals with simple Fourier transforms. In 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC). https:\/\/arxiv."},{"key":"e_1_3_2_1_4_1","unstructured":"org\/pdf\/ 1812.08723.pdf 2019. org\/pdf\/ 1812.08723.pdf 2019."},{"key":"e_1_3_2_1_5_1","volume-title":"Ascending auctions with package bidding. Advances in Theoretical Economics, 1 ( 1 )","author":"Ausubel Lawrence M","year":"2002","unstructured":"[AM02] Lawrence M Ausubel and Paul R Milgrom . Ascending auctions with package bidding. Advances in Theoretical Economics, 1 ( 1 ) , 2002 . [AM02] Lawrence M Ausubel and Paul R Milgrom. Ascending auctions with package bidding. Advances in Theoretical Economics, 1 ( 1 ), 2002."},{"key":"e_1_3_2_1_6_1","volume-title":"A cutting plane algorithm for convex programming that uses analytic centers. Mathematical Programming, 69 ( 1-3 ): 1-43","author":"Atkinson David S","year":"1995","unstructured":"[AV95] David S Atkinson and Pravin M Vaidya . A cutting plane algorithm for convex programming that uses analytic centers. Mathematical Programming, 69 ( 1-3 ): 1-43 , 1995 . [AV95] David S Atkinson and Pravin M Vaidya. A cutting plane algorithm for convex programming that uses analytic centers. Mathematical Programming, 69 ( 1-3 ): 1-43, 1995."},{"key":"e_1_3_2_1_7_1","series-title":"SIAM Journal on Computing, 5 ( 4 ): 624-628","volume-title":"On the number of multiplications required for matrix multiplication","author":"Brockett Roger W","year":"1976","unstructured":"[BD76] Roger W Brockett and David Dobkin . On the number of multiplications required for matrix multiplication . SIAM Journal on Computing, 5 ( 4 ): 624-628 , 1976 . [BD76] Roger W Brockett and David Dobkin. On the number of multiplications required for matrix multiplication. SIAM Journal on Computing, 5 ( 4 ): 624-628, 1976."},{"key":"e_1_3_2_1_8_1","volume-title":"New convex programs and distributed algorithms for fisher markets with linear and spending constraint utilities. Unpublished manuscript","author":"Birnbaum Benjamin","year":"2010","unstructured":"[BDX10] Benjamin Birnbaum , N Devanur , and Lin Xiao . New convex programs and distributed algorithms for fisher markets with linear and spending constraint utilities. Unpublished manuscript , 2010 . [BDX10] Benjamin Birnbaum, N Devanur, and Lin Xiao. New convex programs and distributed algorithms for fisher markets with linear and spending constraint utilities. Unpublished manuscript, 2010."},{"key":"e_1_3_2_1_9_1","volume-title":"Approximation of zonoids by zonotopes. Acta mathematica, 162 ( 1 ): 73-141","author":"Bourgain Jean","year":"1989","unstructured":"[BLM89] Jean Bourgain , Joram Lindenstrauss , and V Milman . Approximation of zonoids by zonotopes. Acta mathematica, 162 ( 1 ): 73-141 , 1989 . [BLM89] Jean Bourgain, Joram Lindenstrauss, and V Milman. Approximation of zonoids by zonotopes. Acta mathematica, 162 ( 1 ): 73-141, 1989."},{"key":"e_1_3_2_1_10_1","volume-title":"52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC). https:\/\/arxiv.org\/ pdf\/ 2002","year":"2020","unstructured":"[BLSS20] Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song. Solving tall dense linear programs in nearly linear time . In 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC). https:\/\/arxiv.org\/ pdf\/ 2002 .02304.pdf, 2020 . [BLSS20] Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song. Solving tall dense linear programs in nearly linear time. In 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC). https:\/\/arxiv.org\/ pdf\/ 2002.02304.pdf, 2020."},{"key":"e_1_3_2_1_11_1","unstructured":"[BNS19] Jan van den Brand Danupon Nanongkai and Thatchaphol Saranurak. [BNS19] Jan van den Brand Danupon Nanongkai and Thatchaphol Saranurak."},{"key":"e_1_3_2_1_12_1","volume-title":"60th Annual IEEE Symposium on Foundations of Computer Science (FOCS). https:\/\/arxiv.org\/pdf\/ 1905","author":"Dynamic","year":"2019","unstructured":"Dynamic matrix inverse : Improved algorithms and matching conditional lower bounds . In 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS). https:\/\/arxiv.org\/pdf\/ 1905 .05067.pdf, 2019 . Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds. In 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS). https:\/\/arxiv.org\/pdf\/ 1905.05067.pdf, 2019."},{"key":"e_1_3_2_1_13_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA). https:\/\/arxiv.org\/pdf\/ 1910.11957","year":"2020","unstructured":"[Bra20] Jan van den Brand. A deterministic linear program solver in current matrix multiplication time . In ACM-SIAM Symposium on Discrete Algorithms (SODA). https:\/\/arxiv.org\/pdf\/ 1910.11957 .pdf, 2020 . [Bra20] Jan van den Brand. A deterministic linear program solver in current matrix multiplication time. In ACM-SIAM Symposium on Discrete Algorithms (SODA). https:\/\/arxiv.org\/pdf\/ 1910.11957.pdf, 2020."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509926"},{"key":"e_1_3_2_1_15_1","first-page":"353","volume-title":"Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC)","author":"Boutsidis Christos","unstructured":"[BW14] Christos Boutsidis and David P Woodruf . Optimal cur matrix decompositions . In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC) , pages 353 - 362 . ACM, https:\/\/arxiv.org\/pdf\/1405. [BW14] Christos Boutsidis and David P Woodruf. Optimal cur matrix decompositions. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 353-362. ACM, https:\/\/arxiv.org\/pdf\/1405."},{"key":"e_1_3_2_1_16_1","volume-title":"Annual Conference on Learning Theory (COLT). https:\/\/arxiv.org\/pdf\/","author":"Cohen Michael B","year":"1905","unstructured":"[CCLY19] Michael B Cohen , Ben Cousins , Yin Tat Lee , and Xin Yang . A nearoptimal algorithm for approximating the John ellipsoid . In Annual Conference on Learning Theory (COLT). https:\/\/arxiv.org\/pdf\/ 1905 .11580. [CCLY19] Michael B Cohen, Ben Cousins, Yin Tat Lee, and Xin Yang. A nearoptimal algorithm for approximating the John ellipsoid. In Annual Conference on Learning Theory (COLT). https:\/\/arxiv.org\/pdf\/ 1905.11580."},{"key":"e_1_3_2_1_17_1","unstructured":"pdf 2019. pdf 2019."},{"key":"e_1_3_2_1_18_1","volume-title":"Vladimir Lysikov, and Jeroen Zuiddam. Barriers for rectangular matrix multiplication. In arXiv preprint. https:\/\/arxiv.org\/","author":"Christandl Matthias","year":"2003","unstructured":"[CGLZ20] Matthias Christandl , Fran\u00e7ois Le Gall , Vladimir Lysikov, and Jeroen Zuiddam. Barriers for rectangular matrix multiplication. In arXiv preprint. https:\/\/arxiv.org\/ 2003 .03019.pdf, 2020. [CGLZ20] Matthias Christandl, Fran\u00e7ois Le Gall, Vladimir Lysikov, and Jeroen Zuiddam. Barriers for rectangular matrix multiplication. In arXiv preprint. https:\/\/arxiv.org\/ 2003.03019.pdf, 2020."},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC). https:\/\/arxiv.","author":"Cohen Michael B","unstructured":"[CLS19] Michael B Cohen , Yin Tat Lee , and Zhao Song . Solving linear programs in the current matrix multiplication time . In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC). https:\/\/arxiv. [CLS19] Michael B Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC). https:\/\/arxiv."},{"key":"e_1_3_2_1_20_1","unstructured":"org\/pdf\/ 1810.07896.pdf 2019. org\/pdf\/ 1810.07896.pdf 2019."},{"key":"e_1_3_2_1_21_1","unstructured":"[CMM17] Michael B Cohen Cameron Musco and Christopher Musco. Input sparsity time low-rank approximation via ridge leverage score sampling. [CMM17] Michael B Cohen Cameron Musco and Christopher Musco. Input sparsity time low-rank approximation via ridge leverage score sampling."},{"key":"e_1_3_2_1_22_1","first-page":"1758","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"In","year":"2017","unstructured":"In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1758 - 1777 . SIAM, https:\/\/arxiv.org\/ pdf\/1511.07263.pdf, 2017 . In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1758-1777. SIAM, https:\/\/arxiv.org\/ pdf\/1511.07263.pdf, 2017."},{"key":"e_1_3_2_1_23_1","series-title":"SIAM Journal on Computing, 11 ( 3 ): 467-471","volume-title":"Rapid multiplication of rectangular matrices","author":"Coppersmith Don","year":"1982","unstructured":"[Cop82] Don Coppersmith . Rapid multiplication of rectangular matrices . SIAM Journal on Computing, 11 ( 3 ): 467-471 , 1982 . [Cop82] Don Coppersmith. Rapid multiplication of rectangular matrices. SIAM Journal on Computing, 11 ( 3 ): 467-471, 1982."},{"key":"e_1_3_2_1_24_1","first-page":"1","author":"Cornet Bernard","year":"1989","unstructured":"[Cor89] Bernard Cornet . Linear exchange economies. Cahier Eco-Math , Universit\u00e9 de Paris , 1 , 1989 . [Cor89] Bernard Cornet. Linear exchange economies. Cahier Eco-Math, Universit\u00e9 de Paris, 1, 1989.","journal-title":"Universit\u00e9 de Paris"},{"key":"e_1_3_2_1_25_1","unstructured":"[CP15] Michael B. Cohen and Richard Peng. \u2113p row sampling by lewis weights. [CP15] Michael B. Cohen and Richard Peng. \u2113p row sampling by lewis weights."},{"key":"e_1_3_2_1_26_1","first-page":"183","volume-title":"Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC)","author":"In","year":"2015","unstructured":"In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC) , pages 183 - 192 . https:\/\/arxiv.org\/pdf\/1412.0588, 2015 . In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), pages 183-192. https:\/\/arxiv.org\/pdf\/1412.0588, 2015."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28396"},{"key":"e_1_3_2_1_28_1","first-page":"81","volume-title":"Symposium on Theory of Computing Conference (STOC)","author":"Kenneth","unstructured":"[CW13] Kenneth L. Clarkson and David P. Woodruf. Low rank approximation and regression in input sparsity time . In Symposium on Theory of Computing Conference (STOC) , pages 81 - 90 . https:\/\/arxiv.org\/pdf\/1207. [CW13] Kenneth L. Clarkson and David P. Woodruf. Low rank approximation and regression in input sparsity time. In Symposium on Theory of Computing Conference (STOC), pages 81-90. https:\/\/arxiv.org\/pdf\/1207."},{"key":"e_1_3_2_1_29_1","volume-title":"Maximization of a linear function of variables subject to linear inequalities. Activity analysis of production and allocation, 13 : 339-347","author":"Dantzig George B","year":"1947","unstructured":"[Dan47] George B Dantzig . Maximization of a linear function of variables subject to linear inequalities. Activity analysis of production and allocation, 13 : 339-347 , 1947 . [Dan47] George B Dantzig. Maximization of a linear function of variables subject to linear inequalities. Activity analysis of production and allocation, 13 : 339-347, 1947."},{"key":"e_1_3_2_1_30_1","first-page":"90","volume-title":"Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (SODA)","author":"Duan Ran","unstructured":"[DGM16] Ran Duan , Jugal Garg , and Kurt Mehlhorn . An improved combinatorial polynomial algorithm for the linear arrow-debreu market . In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (SODA) , pages 90 - 106 . SIAM, https:\/\/arxiv.org\/pdf\/1510.02694. [DGM16] Ran Duan, Jugal Garg, and Kurt Mehlhorn. An improved combinatorial polynomial algorithm for the linear arrow-debreu market. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 90-106. SIAM, https:\/\/arxiv.org\/pdf\/1510.02694."},{"key":"e_1_3_2_1_31_1","unstructured":"pdf 2016. pdf 2016."},{"key":"e_1_3_2_1_32_1","first-page":"6","volume-title":"A rational convex program for linear arrow-debreu markets","author":"Devanur Nikhil R","unstructured":"[DGV16] Nikhil R Devanur , Jugal Garg , and L\u00e1szl\u00f3 A V\u00e9gh . A rational convex program for linear arrow-debreu markets . volume 5 ( 1 ), page 6 . https: \/\/arxiv.org\/pdf\/1307.8037.pdf, 2016. [DGV16] Nikhil R Devanur, Jugal Garg, and L\u00e1szl\u00f3 A V\u00e9gh. A rational convex program for linear arrow-debreu markets. volume 5 ( 1 ), page 6. https: \/\/arxiv.org\/pdf\/1307.8037.pdf, 2016."},{"key":"e_1_3_2_1_33_1","volume-title":"A combinatorial polynomial algorithm for the linear arrow-debreu market. Information and Computation, 243 : 112-132","author":"Duan Ran","year":"2015","unstructured":"[DM15] Ran Duan and Kurt Mehlhorn . A combinatorial polynomial algorithm for the linear arrow-debreu market. Information and Computation, 243 : 112-132 , 2015 . [DM15] Ran Duan and Kurt Mehlhorn. A combinatorial polynomial algorithm for the linear arrow-debreu market. Information and Computation, 243 : 112-132, 2015."},{"key":"e_1_3_2_1_34_1","volume-title":"Fast approximation of matrix coherence and statistical leverage. Journal of Machine Learning Research, 13 (Dec): 3475-3506","author":"Drineas Petros","year":"2012","unstructured":"[DMIMW12] Petros Drineas , Malik Magdon-Ismail , Michael W Mahoney , and David P Woodruf . Fast approximation of matrix coherence and statistical leverage. Journal of Machine Learning Research, 13 (Dec): 3475-3506 , 2012 . [DMIMW12] Petros Drineas, Malik Magdon-Ismail, Michael W Mahoney, and David P Woodruf. Fast approximation of matrix coherence and statistical leverage. Journal of Machine Learning Research, 13 (Dec): 3475-3506, 2012."},{"key":"e_1_3_2_1_35_1","volume-title":"Market equilibrium via a primal-dual algorithm for a convex program. Journal of the ACM (JACM), 55 ( 5 ): 22","author":"Devanur Nikhil R","year":"2008","unstructured":"[DPSV08] Nikhil R Devanur , Christos H Papadimitriou , Amin Saberi , and Vijay V Vazirani . Market equilibrium via a primal-dual algorithm for a convex program. Journal of the ACM (JACM), 55 ( 5 ): 22 , 2008 . [DPSV08] Nikhil R Devanur, Christos H Papadimitriou, Amin Saberi, and Vijay V Vazirani. Market equilibrium via a primal-dual algorithm for a convex program. Journal of the ACM (JACM), 55 ( 5 ): 22, 2008."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0308210511001648"},{"key":"e_1_3_2_1_37_1","volume-title":"On ascending vickrey auctions for heterogeneous objects. Journal of Economic Theory, 132 ( 1 ): 95-118","author":"de Vries Sven","year":"2007","unstructured":"[dVSV07] Sven de Vries , James Schummer , and Rakesh V Vohra . On ascending vickrey auctions for heterogeneous objects. Journal of Economic Theory, 132 ( 1 ): 95-118 , 2007 . [dVSV07] Sven de Vries, James Schummer, and Rakesh V Vohra. On ascending vickrey auctions for heterogeneous objects. Journal of Economic Theory, 132 ( 1 ): 95-118, 2007."},{"key":"e_1_3_2_1_38_1","volume-title":"STANFORD UNIV CALIF SYSTEMS OPTIMIZATION LAB","author":"Eaves B Curtis","year":"1975","unstructured":"[Eav75] B Curtis Eaves . A finite algorithm for the linear exchange model. Technical report , STANFORD UNIV CALIF SYSTEMS OPTIMIZATION LAB , 1975 . [Eav75] B Curtis Eaves. A finite algorithm for the linear exchange model. Technical report, STANFORD UNIV CALIF SYSTEMS OPTIMIZATION LAB, 1975."},{"key":"e_1_3_2_1_39_1","volume-title":"Geometric algorithms and combinatorial optimization","author":"Gr\u00f6tschel Martin","year":"2012","unstructured":"[GLS12] Martin Gr\u00f6tschel , L\u00e1szl\u00f3 Lov\u00e1sz , and Alexander Schrijver . Geometric algorithms and combinatorial optimization , volume 2 . Springer Science & Business Media , 2012 . [GLS12] Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175337"},{"key":"e_1_3_2_1_41_1","first-page":"54","volume-title":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)","author":"Garg Jugal","year":"1809","unstructured":"[GV19] Jugal Garg and L\u00e1szl\u00f3 A V\u00e9gh . A strongly polynomial algorithm for linear exchange markets . In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages 54 - 65 . ACM, https: \/\/arxiv.org\/pdf\/ 1809 .06266.pdf, 2019. [GV19] Jugal Garg and L\u00e1szl\u00f3 A V\u00e9gh. A strongly polynomial algorithm for linear exchange markets. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 54-65. ACM, https: \/\/arxiv.org\/pdf\/ 1809.06266.pdf, 2019."},{"key":"e_1_3_2_1_42_1","unstructured":"[HKNS15] Monika Henzinger Sebastian Krinninger Danupon Nanongkai and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. [HKNS15] Monika Henzinger Sebastian Krinninger Danupon Nanongkai and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture."},{"key":"e_1_3_2_1_43_1","unstructured":"In Proceedings of the forty-seventh annual ACM symposium on Theory of computing (STOC) pages 21-30. ACM https:\/\/arxiv.org\/pdf\/1511.06773. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing (STOC) pages 21-30. ACM https:\/\/arxiv.org\/pdf\/1511.06773."},{"key":"e_1_3_2_1_44_1","unstructured":"pdf 2015. pdf 2015."},{"key":"e_1_3_2_1_45_1","series-title":"SIAM Journal on Computing, 37 ( 1 ): 303-318","volume-title":"A polynomial time algorithm for computing an arrowdebreu market equilibrium for linear utilities","author":"Jain Kamal","year":"2007","unstructured":"[Jai07] Kamal Jain . A polynomial time algorithm for computing an arrowdebreu market equilibrium for linear utilities . SIAM Journal on Computing, 37 ( 1 ): 303-318 , 2007 . [Jai07] Kamal Jain. A polynomial time algorithm for computing an arrowdebreu market equilibrium for linear utilities. SIAM Journal on Computing, 37 ( 1 ): 303-318, 2007."},{"key":"e_1_3_2_1_46_1","volume-title":"Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26 ( 189-206): 1","author":"Johnson William B","year":"1984","unstructured":"[JL84] William B Johnson and Joram Lindenstrauss . Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26 ( 189-206): 1 , 1984 . [JL84] William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26 ( 189-206): 1, 1984."},{"key":"e_1_3_2_1_47_1","volume-title":"Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization, convex-concave games and its applications. In STOC. https:\/\/arxiv.org\/pdf\/","author":"Jiang Haotian","year":"2004","unstructured":"[JLSW20] Haotian Jiang , Yin Tat Lee , Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization, convex-concave games and its applications. In STOC. https:\/\/arxiv.org\/pdf\/ 2004 .04250. [JLSW20] Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong. An improved cutting plane method for convex optimization, convex-concave games and its applications. In STOC. https:\/\/arxiv.org\/pdf\/ 2004.04250."},{"key":"e_1_3_2_1_48_1","unstructured":"pdf 2020. pdf 2020."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808695"},{"key":"e_1_3_2_1_50_1","unstructured":"[Kha80] Leonid G Khachiyan. Polynomial algorithms in linear programming. [Kha80] Leonid G Khachiyan. Polynomial algorithms in linear programming."},{"key":"e_1_3_2_1_51_1","volume-title":"53-72","author":"Computational Mathematics USSR","year":"1980","unstructured":"USSR Computational Mathematics and Mathematical Physics , 20 ( 1 ) : 53-72 , 1980 . USSR Computational Mathematics and Mathematical Physics, 20 ( 1 ): 53-72, 1980."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913392"},{"key":"e_1_3_2_1_53_1","first-page":"226","volume":"37","author":"Khachiyan Leonid G","year":"1988","unstructured":"[KTE88] Leonid G Khachiyan , Sergei Pavlovich Tarasov , and I. I. Erlikh . The method of inscribed ellipsoids. In Soviet Math. Dokl , volume 37 , pages 226 - 230 , 1988 . [KTE88] Leonid G Khachiyan, Sergei Pavlovich Tarasov, and I. I. Erlikh. The method of inscribed ellipsoids. In Soviet Math. Dokl, volume 37, pages 226-230, 1988.","journal-title":"The method of inscribed ellipsoids. In Soviet Math. Dokl"},{"key":"e_1_3_2_1_54_1","volume-title":"Simulated annealing for convex optimization. Mathematics of Operations Research, 31 ( 2 ): 253-266","author":"Kalai Adam Tauman","year":"2006","unstructured":"[KV06] Adam Tauman Kalai and Santosh Vempala . Simulated annealing for convex optimization. Mathematics of Operations Research, 31 ( 2 ): 253-266 , 2006 . [KV06] Adam Tauman Kalai and Santosh Vempala. Simulated annealing for convex optimization. Mathematics of Operations Research, 31 ( 2 ): 253-266, 2006."},{"key":"e_1_3_2_1_55_1","first-page":"369","volume-title":"Advances in neural information processing systems (NIPS)","author":"Lu Yichao","year":"2013","unstructured":"[LDFU13] Yichao Lu , Paramveer Dhillon , Dean P Foster , and Lyle Ungar . Faster ridge regression via the subsampled randomized hadamard transform . In Advances in neural information processing systems (NIPS) , pages 369 - 377 , 2013 . [LDFU13] Yichao Lu, Paramveer Dhillon, Dean P Foster, and Lyle Ungar. Faster ridge regression via the subsampled randomized hadamard transform. In Advances in neural information processing systems (NIPS), pages 369-377, 2013."},{"key":"e_1_3_2_1_56_1","unstructured":"[Lee16] Yin Tat Lee. Faster algorithms for convex and combinatorial optimization. [Lee16] Yin Tat Lee. Faster algorithms for convex and combinatorial optimization."},{"key":"e_1_3_2_1_57_1","volume-title":"Massachusetts Institute of Technology","author":"D","year":"2016","unstructured":"Ph D thesis , Massachusetts Institute of Technology , 2016 . PhD thesis, Massachusetts Institute of Technology, 2016."},{"key":"e_1_3_2_1_58_1","volume-title":"Finite dimensional subspaces of \u2113p. Studia Mathematica, 63 ( 2 ): 207-212","author":"Lewis D.","year":"1978","unstructured":"[Lew78] D. Lewis . Finite dimensional subspaces of \u2113p. Studia Mathematica, 63 ( 2 ): 207-212 , 1978 . [Lew78] D. Lewis. Finite dimensional subspaces of \u2113p. Studia Mathematica, 63 ( 2 ): 207-212, 1978."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_3_2_1_61_1","first-page":"230","volume-title":"56th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Lee Yin Tat","unstructured":"[LS15] Yin Tat Lee and Aaron Sidford . Eficient inverse maintenance and faster algorithms for linear programming . In 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 230 - 249 . https:\/\/arxiv. [LS15] Yin Tat Lee and Aaron Sidford. Eficient inverse maintenance and faster algorithms for linear programming. In 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 230-249. https:\/\/arxiv."},{"key":"e_1_3_2_1_62_1","unstructured":"org\/pdf\/1503.01752.pdf 2015. org\/pdf\/1503.01752.pdf 2015."},{"key":"e_1_3_2_1_63_1","unstructured":"[LSS+20] Jason Lee Ruoqi Shen Zhao Song Mengdi Wang and Zheng Yu. Leverage score sampling neural tangent kernel and kernel ridge regression. [LSS+20] Jason Lee Ruoqi Shen Zhao Song Mengdi Wang and Zheng Yu. Leverage score sampling neural tangent kernel and kernel ridge regression."},{"key":"e_1_3_2_1_64_1","unstructured":"In Manuscript 2020. In Manuscript 2020."},{"key":"e_1_3_2_1_65_1","volume-title":"Annual Conference on Learning Theory (COLT). https:\/\/arxiv.org\/pdf\/1706","author":"Lee Yin Tat","year":"2018","unstructured":"[LSV18] Yin Tat Lee , Aaron Sidford , and Santosh S Vempala . Eficient convex optimization with membership oracles . In Annual Conference on Learning Theory (COLT). https:\/\/arxiv.org\/pdf\/1706 .07357.pdf, 2018 . [LSV18] Yin Tat Lee, Aaron Sidford, and Santosh S Vempala. Eficient convex optimization with membership oracles. In Annual Conference on Learning Theory (COLT). https:\/\/arxiv.org\/pdf\/1706.07357.pdf, 2018."},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.68"},{"key":"e_1_3_2_1_67_1","volume-title":"Annual Conference on Learning Theory (COLT). https:\/\/arxiv.org\/pdf\/ 1905","author":"Lee Yin Tat","year":"2019","unstructured":"[LSZ19] Yin Tat Lee , Zhao Song , and Qiuyi Zhang . Solving empirical risk minimization in the current matrix multiplication time . In Annual Conference on Learning Theory (COLT). https:\/\/arxiv.org\/pdf\/ 1905 .04447, 2019 . [LSZ19] Yin Tat Lee, Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization in the current matrix multiplication time. In Annual Conference on Learning Theory (COLT). https:\/\/arxiv.org\/pdf\/ 1905.04447, 2019."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.28"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.42"},{"key":"e_1_3_2_1_70_1","first-page":"253","volume-title":"54th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Madry Aleksander","unstructured":"[Mad13] Aleksander Madry . Navigating central path with electrical flows: From lfows to matchings, and back . In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 253 - 262 . https:\/\/arxiv. [Mad13] Aleksander Madry. Navigating central path with electrical flows: From lfows to matchings, and back. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 253-262. https:\/\/arxiv."},{"key":"e_1_3_2_1_71_1","unstructured":"org\/pdf\/1307.2205.pdf 2013. org\/pdf\/1307.2205.pdf 2013."},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.70"},{"key":"e_1_3_2_1_73_1","volume-title":"Eficient methods in convex programming. Lecture notes","author":"Nemirovski Arkadi","year":"1994","unstructured":"[Nem94] Arkadi Nemirovski . Eficient methods in convex programming. Lecture notes , 1994 . [Nem94] Arkadi Nemirovski. Eficient methods in convex programming. Lecture notes, 1994."},{"key":"e_1_3_2_1_74_1","volume-title":"Self-concordant functions and polynomial time methods in convex programming. preprint, central economic & mathematical institute, ussr acad. Sci","author":"Nesterov YE","year":"1989","unstructured":"[NN89] YE Nesterov and AS Nemirovskii . Self-concordant functions and polynomial time methods in convex programming. preprint, central economic & mathematical institute, ussr acad. Sci . Moscow , USSR , 1989 . [NN89] YE Nesterov and AS Nemirovskii. Self-concordant functions and polynomial time methods in convex programming. preprint, central economic & mathematical institute, ussr acad. Sci. Moscow, USSR, 1989."},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.21"},{"key":"e_1_3_2_1_76_1","volume-title":"One algorithm for finding solutions of the arrow-debreu model. Kibernetica, 3 : 127-128","author":"Nenakov EI","year":"1983","unstructured":"[NP83] EI Nenakov and ME Primak . One algorithm for finding solutions of the arrow-debreu model. Kibernetica, 3 : 127-128 , 1983 . [NP83] EI Nenakov and ME Primak. One algorithm for finding solutions of the arrow-debreu model. Kibernetica, 3 : 127-128, 1983."},{"key":"e_1_3_2_1_77_1","volume-title":"Problem complexity and method eficiency in optimization","author":"Nemirovsky Arkadii Semenovich","year":"1983","unstructured":"[NY83] Arkadii Semenovich Nemirovsky and David Borisovich Yudin . Problem complexity and method eficiency in optimization . 1983 . [NY83] Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method eficiency in optimization. 1983."},{"key":"e_1_3_2_1_78_1","unstructured":"[Par99] David C Parkes. ibundle: An eficient ascending price bundle auction. [Par99] David C Parkes. ibundle: An eficient ascending price bundle auction."},{"key":"e_1_3_2_1_79_1","volume-title":"Algorithms for approximate calculation of the minimum of a convex function from its values. Mathematical Notes, 59 ( 1 ): 69-74","author":"Protasov V Yu","year":"1996","unstructured":"[Pro96] V Yu Protasov . Algorithms for approximate calculation of the minimum of a convex function from its values. Mathematical Notes, 59 ( 1 ): 69-74 , 1996 . [Pro96] V Yu Protasov. Algorithms for approximate calculation of the minimum of a convex function from its values. Mathematical Notes, 59 ( 1 ): 69-74, 1996."},{"key":"e_1_3_2_1_80_1","volume-title":"International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Price Eric","year":"2017","unstructured":"[PSW17] Eric Price , Zhao Song , and David P. Woodruf . Fast regression with an \u2113\u221e guarantee . In International Colloquium on Automata, Languages, and Programming (ICALP) , 2017 . [PSW17] Eric Price, Zhao Song, and David P. Woodruf. Fast regression with an \u2113\u221e guarantee. In International Colloquium on Automata, Languages, and Programming (ICALP), 2017."},{"key":"e_1_3_2_1_81_1","volume-title":"An ascending-price generalized vickrey auction","author":"Parkes David C","year":"2002","unstructured":"[PU02] David C Parkes and Lyle H Ungar . An ascending-price generalized vickrey auction . 2002 . [PU02] David C Parkes and Lyle H Ungar. An ascending-price generalized vickrey auction. 2002."},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897639"},{"key":"e_1_3_2_1_83_1","unstructured":"[San04] Piotr Sankowski. Dynamic transitive closure via dynamic matrix inverse. [San04] Piotr Sankowski. Dynamic transitive closure via dynamic matrix inverse."},{"key":"e_1_3_2_1_84_1","first-page":"509","volume-title":"45th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"In","year":"2004","unstructured":"In 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 509 - 517 . IEEE, 2004 . In 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 509-517. IEEE, 2004."},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188852"},{"key":"e_1_3_2_1_86_1","volume-title":"Cut-of method with space extension in convex programming problems. Cybernetics and systems analysis, 13 ( 1 ): 94-96","author":"Shor Naum Z","year":"1977","unstructured":"[Sho77] Naum Z Shor . Cut-of method with space extension in convex programming problems. Cybernetics and systems analysis, 13 ( 1 ): 94-96 , 1977 . [Sho77] Naum Z Shor. Cut-of method with space extension in convex programming problems. Cybernetics and systems analysis, 13 ( 1 ): 94-96, 1977."},{"key":"e_1_3_2_1_88_1","unstructured":"[Son19] Zhao Song. Matrix Theory : Optimization Concentration and Algorithms. [Son19] Zhao Song. Matrix Theory : Optimization Concentration and Algorithms."},{"key":"e_1_3_2_1_89_1","volume-title":"The University of Texas at Austin","author":"D","year":"2019","unstructured":"Ph D thesis , The University of Texas at Austin , 2019 . PhD thesis, The University of Texas at Austin, 2019."},{"key":"e_1_3_2_1_90_1","series-title":"SIAM Journal on Computing","first-page":"1913","volume-title":"Graph sparsification by effective resistances","author":"Spielman Daniel A","year":"2011","unstructured":"[SS11] Daniel A Spielman and Nikhil Srivastava . Graph sparsification by effective resistances . In SIAM Journal on Computing , volume 40 ( 6 ), pages 1913 - 1926 . https:\/\/arxiv.org\/pdf\/0803.0929.pdf, 2011 . [SS11] Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. In SIAM Journal on Computing, volume 40 ( 6 ), pages 1913-1926. https:\/\/arxiv.org\/pdf\/0803.0929.pdf, 2011."},{"key":"e_1_3_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055431"},{"key":"e_1_3_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.172"},{"key":"e_1_3_2_1_93_1","volume-title":"28th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Vaidya Pravin M","year":"1987","unstructured":"[Vai87] Pravin M Vaidya . An algorithm for linear programming which requires o(((m + n)n2 + (m + n)1.5n) l ) arithmetic operations . In 28th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , 1987 . [Vai87] Pravin M Vaidya. An algorithm for linear programming which requires o(((m + n)n2 + (m + n)1.5n) l ) arithmetic operations. In 28th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1987."},{"key":"e_1_3_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63500"},{"key":"e_1_3_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63499"},{"key":"e_1_3_2_1_96_1","volume-title":"Spending constraint utilities with applications to the adwords market. Mathematics of Operations Research, 35 ( 2 ): 458-478","author":"Vazirani Vijay V","year":"2010","unstructured":"[Vaz10] Vijay V Vazirani . Spending constraint utilities with applications to the adwords market. Mathematics of Operations Research, 35 ( 2 ): 458-478 , 2010 . [Vaz10] Vijay V Vazirani. Spending constraint utilities with applications to the adwords market. Mathematics of Operations Research, 35 ( 2 ): 458-478, 2010."},{"key":"e_1_3_2_1_97_1","first-page":"1729","volume-title":"A strongly polynomial algorithm for a class of minimumcost flow problems with separable convex objectives","author":"V\u00e9gh L\u00e1szl\u00f3 A","year":"2016","unstructured":"[V\u00e9g16] L\u00e1szl\u00f3 A V\u00e9gh . A strongly polynomial algorithm for a class of minimumcost flow problems with separable convex objectives . volume 45 ( 5 ), pages 1729 - 1761 . https:\/\/arxiv.org\/pdf\/1110.4882.pdf, 2016 . [V\u00e9g16] L\u00e1szl\u00f3 A V\u00e9gh. A strongly polynomial algorithm for a class of minimumcost flow problems with separable convex objectives. volume 45 ( 5 ), pages 1729-1761. https:\/\/arxiv.org\/pdf\/1110.4882.pdf, 2016."},{"key":"e_1_3_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_3_2_1_100_1","unstructured":"[Ye08] Yinyu Ye. A path to the arrow-debreu competitive market equilibrium. [Ye08] Yinyu Ye. A path to the arrow-debreu competitive market equilibrium."},{"key":"e_1_3_2_1_101_1","volume-title":"315-348","author":"Programming Mathematical","year":"2008","unstructured":"Mathematical Programming , 111 ( 1-2 ) : 315-348 , 2008 . Mathematical Programming, 111 ( 1-2 ): 315-348, 2008."},{"key":"e_1_3_2_1_102_1","volume-title":"Evaluation of the information complexity of mathematical programming problems. Ekonomika i Matematicheskie Metody, 12 : 128-142","author":"Yudin David B","year":"1976","unstructured":"[YN76] David B Yudin and Arkadii S Nemirovski . Evaluation of the information complexity of mathematical programming problems. Ekonomika i Matematicheskie Metody, 12 : 128-142 , 1976 . [YN76] David B Yudin and Arkadii S Nemirovski. Evaluation of the information complexity of mathematical programming problems. Ekonomika i Matematicheskie Metody, 12 : 128-142, 1976."}],"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\/pdf\/10.1145\/3357713.3384284","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T21:13:07Z","timestamp":1673298787000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384284"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":100,"alternative-id":["10.1145\/3357713.3384284","10.1145\/3357713"],"URL":"http:\/\/dx.doi.org\/10.1145\/3357713.3384284","relation":{},"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}