{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:01:33Z","timestamp":1772906493574,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":65,"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"}],"funder":[{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["715672"],"award-info":[{"award-number":["715672"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1749609, CCF-1740551, DMS-1839116, CCF-1844855"],"award-info":[{"award-number":["CCF-1749609, CCF-1740551, DMS-1839116, CCF-1844855"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384309","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"775-788","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Solving tall dense linear programs in nearly linear time"],"prefix":"10.1145","author":[{"given":"Jan","family":"van den Brand","sequence":"first","affiliation":[{"name":"KTH, Sweden"}]},{"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Washington, USA \/ Microsoft Research, USA"}]},{"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Zhao","family":"Song","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study at Princeton, USA \/ Princeton University, 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.1137\/1.9781611975482.86"},{"key":"e_1_3_2_1_2_1","volume-title":"APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings. 1\u201310","author":"Ahn Kook Jin","year":"2013","unstructured":"Kook Jin Ahn , Sudipto Guha , and Andrew McGregor . 2013 . Spectral Sparsification in Dynamic Graph Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop , APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings. 1\u201310 . Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. 2013. Spectral Sparsification in Dynamic Graph Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings. 1\u201310."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614386"},{"key":"e_1_3_2_1_4_1","volume-title":"Approximation of zonoids by zonotopes. Acta mathematica, 162, 1","author":"Bourgain Jean","year":"1989","unstructured":"Jean Bourgain , Joram Lindenstrauss , and V Milman . 1989. Approximation of zonoids by zonotopes. Acta mathematica, 162, 1 ( 1989 ), 73\u2013141. Jean Bourgain, Joram Lindenstrauss, and V Milman. 1989. Approximation of zonoids by zonotopes. Acta mathematica, 162, 1 (1989), 73\u2013141."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.16"},{"key":"e_1_3_2_1_6_1","volume-title":"Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds. In 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS). arxiv:1905","author":"van den Brand Jan","year":"2019","unstructured":"Jan van den Brand , Danupon Nanongkai , and Thatchaphol Saranurak . 2019 . Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds. In 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS). arxiv:1905 .05067 Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak. 2019. Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds. In 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS). arxiv:1905.05067"},{"key":"e_1_3_2_1_7_1","volume-title":"Stable signal recovery from incomplete and inaccurate measurements. Communications on pure and applied mathematics, 59, 8","author":"Candes Emmanuel J","year":"2006","unstructured":"Emmanuel J Candes , Justin K Romberg , and Terence Tao . 2006. Stable signal recovery from incomplete and inaccurate measurements. Communications on pure and applied mathematics, 59, 8 ( 2006 ), 1207\u20131223. Emmanuel J Candes, Justin K Romberg, and Terence Tao. 2006. Stable signal recovery from incomplete and inaccurate measurements. Communications on pure and applied mathematics, 59, 8 (2006), 1207\u20131223."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Moses Charikar Kevin Chen and Martin Farach-Colton. 2002. Finding frequent items in data streams. In International Colloquium on Automata Languages and Programming (ICALP). 693\u2013703.  Moses Charikar Kevin Chen and Martin Farach-Colton. 2002. Finding frequent items in data streams. In International Colloquium on Automata Languages and Programming (ICALP). 693\u2013703.","DOI":"10.1007\/3-540-45465-9_59"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488620"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884456"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688113"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316303"},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, (STOC). arxiv:1412","author":"Michael","unstructured":"Michael B. Cohen and Richard Peng. 2015. \u2113 _p Row Sampling by Lewis Weights . In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, (STOC). arxiv:1412 .0588 183\u2013192. Michael B. Cohen and Richard Peng. 2015. \u2113 _p Row Sampling by Lewis Weights. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, (STOC). arxiv:1412.0588 183\u2013192."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211038"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1562764.1562789"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24698-5_7"},{"key":"e_1_3_2_1_18_1","volume-title":"Maximization of a linear function of variables subject to linear inequalities","author":"Dantzig George B","unstructured":"George B Dantzig . 1951. Maximization of a linear function of variables subject to linear inequalities . New York . George B Dantzig. 1951. Maximization of a linear function of variables subject to linear inequalities. New York."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316379"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Fran\u00e7ois Le Gall. 2014. Powers of tensors and fast matrix multiplication. In ISSAC.  Fran\u00e7ois Le Gall. 2014. Powers of tensors and fast matrix multiplication. In ISSAC.","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.67"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806755"},{"key":"e_1_3_2_1_24_1","series-title":"SIAM review, 34, 2","volume-title":"Path-following methods for linear programming","author":"Gonzaga Clovis C","year":"1992","unstructured":"Clovis C Gonzaga . 1992. Path-following methods for linear programming . SIAM review, 34, 2 ( 1992 ), 167\u2013224. Clovis C Gonzaga. 1992. Path-following methods for linear programming. SIAM review, 34, 2 (1992), 167\u2013224."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993735"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/141002281"},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). arxiv:1903","author":"Kapralov Michael","year":"2020","unstructured":"Michael Kapralov , Navid Nouri , Aaron Sidford , and Jakab Tardos . 2020 . Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space . In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). arxiv:1903 .12150 Michael Kapralov, Navid Nouri, Aaron Sidford, and Jakab Tardos. 2020. Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). arxiv:1903.12150"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808695"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(80)90061-0"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.16"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_3_2_1_34_1","volume-title":"Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS). arxiv:1503","author":"Lee Yin Tat","year":"2015","unstructured":"Yin Tat Lee and Aaron Sidford . 2015 . Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS). arxiv:1503 .01752 230\u2013249. Yin Tat Lee and Aaron Sidford. 2015. Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. In 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS). arxiv:1503.01752 230\u2013249."},{"key":"e_1_3_2_1_35_1","unstructured":"Yin Tat Lee and Aaron Sidford. 2019. Solving Linear Programs with \u221a rank Linear System Solves. In arXiv preprint. arxiv:1910.08033 Journal submission.  Yin Tat Lee and Aaron Sidford. 2019. Solving Linear Programs with \u221a rank Linear System Solves. In arXiv preprint. arxiv:1910.08033 Journal submission."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.68"},{"key":"e_1_3_2_1_37_1","volume-title":"Solving Empirical Risk Minimization in the Current Matrix Multiplication Time. In Conference on Learning Theory (COLT). arxiv:1905","author":"Lee Yin Tat","year":"2019","unstructured":"Yin Tat Lee , Zhao Song , and Qiuyi Zhang . 2019 . Solving Empirical Risk Minimization in the Current Matrix Multiplication Time. In Conference on Learning Theory (COLT). arxiv:1905 .04447 2140\u20132157. Yin Tat Lee, Zhao Song, and Qiuyi Zhang. 2019. Solving Empirical Risk Minimization in the Current Matrix Multiplication Time. In Conference on Learning Theory (COLT). arxiv:1905.04447 2140\u20132157."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4064\/sm-63-2-207-212"},{"key":"e_1_3_2_1_39_1","volume-title":"Iterative Row Sampling. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS). arxiv:1211","author":"Li Mu","year":"2013","unstructured":"Mu Li , Gary L. Miller , and Richard Peng . 2013 . Iterative Row Sampling. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS). arxiv:1211 .2713 127\u2013136. Mu Li, Gary L. Miller, and Richard Peng. 2013. Iterative Row Sampling. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS). arxiv:1211.2713 127\u2013136."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000035"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0802028"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488621"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316355"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.21"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Jelani Nelson Huy L Nguy\u00ean and David P Woodruff. 2014. On deterministic sketching and streaming for sparse recovery and norm estimation. In Linear Algebra and its Applications. 441 arxiv:1206.5725 152\u2013167.  Jelani Nelson Huy L Nguy\u00ean and David P Woodruff. 2014. On deterministic sketching and streaming for sparse recovery and norm estimation. In Linear Algebra and its Applications. 441 arxiv:1206.5725 152\u2013167.","DOI":"10.1016\/j.laa.2012.12.025"},{"key":"e_1_3_2_1_46_1","volume-title":"Woodruff","author":"Nelson Jelani","year":"2014","unstructured":"Jelani Nelson and David P . Woodruff . 2014 . Personal communication. .. Jelani Nelson and David P. Woodruff. 2014. Personal communication. .."},{"key":"e_1_3_2_1_47_1","volume-title":"Interior-point polynomial algorithms in convex programming. 13","author":"Nesterov Yurii","unstructured":"Yurii Nesterov and Arkadii Semenovich Nemirovskii . 1994. Interior-point polynomial algorithms in convex programming. 13 , Society for Industrial and Applied Mathematics . Yurii Nesterov and Arkadii Semenovich Nemirovskii. 1994. Interior-point polynomial algorithms in convex programming. 13, Society for Industrial and Applied Mathematics."},{"key":"e_1_3_2_1_48_1","volume-title":"Self-concordant functions and polynomial-time methods in convex programming","author":"Nesterov Yu","unstructured":"Yu Nesterov and Arkadi Nemirovskiy . 1989. Self-concordant functions and polynomial-time methods in convex programming . USSR Academy of Sciences, Central Economic & Mathematic Institute . Yu Nesterov and Arkadi Nemirovskiy. 1989. Self-concordant functions and polynomial-time methods in convex programming. USSR Academy of Sciences, Central Economic & Mathematic Institute."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801033"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2493252.2493254"},{"key":"e_1_3_2_1_52_1","first-page":"1","article-title":"A polynomial-time algorithm, based on Newton\u2019s method, for linear programming","volume":"40","author":"Renegar James","year":"1988","unstructured":"James Renegar . 1988 . A polynomial-time algorithm, based on Newton\u2019s method, for linear programming . Mathematical Programming , 40 , 1 - 3 (1988), 59\u201393. James Renegar. 1988. A polynomial-time algorithm, based on Newton\u2019s method, for linear programming. Mathematical Programming, 40, 1-3 (1988), 59\u201393.","journal-title":"Mathematical Programming"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.25"},{"key":"e_1_3_2_1_55_1","unstructured":"Zhao Song. 2019. Matrix Theory: Optimization Concentration and Algorithms. Ph.D. Dissertation. The University of Texas at Austin.  Zhao Song. 2019. Matrix Theory: Optimization Concentration and Algorithms. Ph.D. Dissertation. The University of Texas at Austin."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.172"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734029"},{"key":"e_1_3_2_1_58_1","unstructured":"Andrew James Stothers. 2010. On the complexity of matrix multiplication.  Andrew James Stothers. 2010. On the complexity of matrix multiplication."},{"key":"e_1_3_2_1_59_1","volume-title":"Gaussian elimination is not optimal. Numerische mathematik, 13, 4","author":"Strassen Volker","year":"1969","unstructured":"Volker Strassen . 1969. Gaussian elimination is not optimal. Numerische mathematik, 13, 4 ( 1969 ), 354\u2013356. Volker Strassen. 1969. Gaussian elimination is not optimal. Numerische mathematik, 13, 4 (1969), 354\u2013356."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.52"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63500"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63499"},{"key":"e_1_3_2_1_63_1","volume-title":"31st Annual IEEE Symposium on Foundations of Computer Science (FOCS). 583\u2013589","author":"Vaidya Pravin M.","year":"1990","unstructured":"Pravin M. Vaidya . 1990 . Reducing the Parallel Complexity of Certain Linear Programming Problems (Extended Abstract) . In 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS). 583\u2013589 . Pravin M. Vaidya. 1990. Reducing the Parallel Complexity of Certain Linear Programming Problems (Extended Abstract). In 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS). 583\u2013589."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"crossref","unstructured":"Pravin M Vaidya and David S Atkinson. 1993. A technique for bounding the number of iterations in path following algorithms. Complexity in Numerical Optimization 462\u2013489.  Pravin M Vaidya and David S Atkinson. 1993. A technique for bounding the number of iterations in path following algorithms. Complexity in Numerical Optimization 462\u2013489.","DOI":"10.1142\/9789814354363_0021"},{"key":"e_1_3_2_1_65_1","volume-title":"Aaron Sidford, and Zhao Song.","author":"van den Brand Jan","year":"2020","unstructured":"Jan van den Brand , Yin Tat Lee , Aaron Sidford, and Zhao Song. 2020 . Solving Tall Dense Linear Programs in Nearly Linear Time. CoRR , abs\/2002.02304 (2020). Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song. 2020. Solving Tall Dense Linear Programs in Nearly Linear Time. CoRR, abs\/2002.02304 (2020)."},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000060"},{"key":"e_1_3_2_1_68_1","volume-title":"Interior point algorithms: theory and analysis. 44","author":"Yinyu Ye.","unstructured":"Yinyu Ye. 2011. Interior point algorithms: theory and analysis. 44 , John Wiley & Sons . Yinyu Ye. 2011. Interior point algorithms: theory and analysis. 44, John Wiley & Sons."},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.1.53"}],"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.3384309","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384309","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:13Z","timestamp":1750200073000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384309"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":65,"alternative-id":["10.1145\/3357713.3384309","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384309","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"}}]}}