{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:25:02Z","timestamp":1750220702606,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":53,"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.3384338","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"789-802","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Positive semidefinite programming: mixed, parallel, and width-independent"],"prefix":"10.1145","author":[{"given":"Arun","family":"Jambulapati","sequence":"first","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Yin Tat","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Washington, USA \/ Microsoft Research, USA"}]},{"given":"Jerry","family":"Li","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}]},{"given":"Swati","family":"Padmanabhan","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}]},{"given":"Kevin","family":"Tian","sequence":"additional","affiliation":[{"name":"Stanford 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.4086\/toc.2012.v008a006"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.85"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250823"},{"key":"e_1_3_2_1_4_1","first-page":"125","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML 2017","author":"Allen-Zhu Zeyuan","year":"2017","unstructured":"Zeyuan Allen-Zhu and Yuanzhi Li . Follow the compressed leader: Faster online learning of eigenvectors and faster MMWU . In Proceedings of the 34th International Conference on Machine Learning, ICML 2017 , Sydney, NSW, Australia , 6-11 August 2017 , pages 116\u2013 125 , 2017. Zeyuan Allen-Zhu and Yuanzhi Li. Follow the compressed leader: Faster online learning of eigenvectors and faster MMWU. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 116\u2013125, 2017."},{"key":"e_1_3_2_1_5_1","first-page":"1831","volume-title":"Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016","author":"Zhu Zeyuan Allen","year":"2016","unstructured":"Zeyuan Allen Zhu , Yin Tat Lee , and Lorenzo Orecchia . Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver . In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 , Arlington, VA, USA , January 10-12, 2016 , pages 1824\u2013 1831 , 2016. Zeyuan Allen Zhu, Yin Tat Lee, and Lorenzo Orecchia. Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1824\u20131831, 2016."},{"key":"e_1_3_2_1_6_1","first-page":"236","volume-title":"Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015","author":"Zhu Zeyuan Allen","year":"2015","unstructured":"Zeyuan Allen Zhu and Lorenzo Orecchia . Nearly-linear time positive LP solver with faster convergence rate . In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015 , Portland, OR, USA , June 14-17, 2015 , pages 229\u2013 236 , 2015. Zeyuan Allen Zhu and Lorenzo Orecchia. Nearly-linear time positive LP solver with faster convergence rate. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 229\u2013236, 2015."},{"key":"e_1_3_2_1_7_1","first-page":"1456","volume-title":"Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015","author":"Zhu Zeyuan Allen","year":"2015","unstructured":"Zeyuan Allen Zhu and Lorenzo Orecchia . Using optimization to break the epsilon barrier: A faster and simpler width-independent algorithm for solving positive linear programs in parallel . In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 , San Diego, CA, USA , January 4-6, 2015 , pages 1439\u2013 1456 , 2015. Zeyuan Allen Zhu and Lorenzo Orecchia. Using optimization to break the epsilon barrier: A faster and simpler width-independent algorithm for solving positive linear programs in parallel. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1439\u20131456, 2015."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_3_2_1_9_1","volume-title":"Personal communication","author":"Allen-Zhu Zeyuan","year":"2019","unstructured":"Zeyuan Allen-Zhu . Personal communication , 2019 . Zeyuan Allen-Zhu. Personal communication, 2019."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085801X"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.171"},{"key":"e_1_3_2_1_12_1","volume-title":"Conference on Learning Theory, COLT 2019","author":"Carmon Yair","year":"2019","unstructured":"Yair Carmon , John C. Duchi , Aaron Sidford , and Kevin Tian . A rank-1 sketch for matrix multiplicative weights . In Conference on Learning Theory, COLT 2019 , 25-28 June 2019 , Phoenix, AZ, USA, pages 589\u2013623 , 2019. Yair Carmon, John C. Duchi, Aaron Sidford, and Kevin Tian. A rank-1 sketch for matrix multiplicative weights. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, pages 589\u2013623, 2019."},{"key":"e_1_3_2_1_13_1","first-page":"1394","volume-title":"Conference On Learning Theory, COLT 2018","author":"Cheng Yu","year":"2018","unstructured":"Yu Cheng and Rong Ge . Non-convex matrix completion against a semi-random adversary . In Conference On Learning Theory, COLT 2018 , Stockholm, Sweden , 6-9 July 2018 ., pages 1362\u2013 1394 , 2018. Yu Cheng and Rong Ge. Non-convex matrix completion against a semi-random adversary. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018., pages 1362\u20131394, 2018."},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the Thirty-third Annual Conference on Neural Information Processing Systems","author":"Carmon Yair","year":"2019","unstructured":"Yair Carmon , Yujia Jin , Aaron Sidford , and Kevin Tian . Variance reduction for matrix games. In Advances in Neural Information Processing Systems 33 , Proceedings of the Thirty-third Annual Conference on Neural Information Processing Systems , Vancouver, British Columbia, Canada , December 8-14, 2019 , 2019. Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. Variance reduction for matrix games. In Advances in Neural Information Processing Systems 33, Proceedings of the Thirty-third Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8-14, 2019, 2019."},{"key":"e_1_3_2_1_15_1","first-page":"568","volume-title":"Proceedings of the 32nd International Conference on Machine Learning, ICML 2015","author":"Garber Dan","year":"2015","unstructured":"Dan Garber , Elad Hazan , and Tengyu Ma . Online learning of eigenvectors . In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015 , Lille, France , 6-11 July 2015 , pages 560\u2013 568 , 2015. Dan Garber, Elad Hazan, and Tengyu Ma. Online learning of eigenvectors. In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, pages 560\u2013568, 2015."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(95)00032-0"},{"key":"e_1_3_2_1_17_1","first-page":"B1127","article-title":"Lower bounds for the helmholtz function. Physical Review","volume":"137","author":"Golden Sidney","year":"1965","unstructured":"Sidney Golden . Lower bounds for the helmholtz function. Physical Review , Series II , 137 (4B): B1127 \u2013 B1128 , 1965 . Sidney Golden. Lower bounds for the helmholtz function. Physical Review, Series II, 137(4B):B1127\u2013B1128, 1965.","journal-title":"Series II"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/090762671"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049697.2049704"},{"key":"e_1_3_2_1_21_1","volume-title":"Efficient structured matrix recovery and nearly-linear time algorithms for solving inverse symmetric m-matrices. CoRR, abs\/1812.06295","author":"Jambulapati Arun","year":"2018","unstructured":"Arun Jambulapati , Kirankumar Shiragur , and Aaron Sidford . Efficient structured matrix recovery and nearly-linear time algorithms for solving inverse symmetric m-matrices. CoRR, abs\/1812.06295 , 2018 . Arun Jambulapati, Kirankumar Shiragur, and Aaron Sidford. Efficient structured matrix recovery and nearly-linear time algorithms for solving inverse symmetric m-matrices. CoRR, abs\/1812.06295, 2018."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.25"},{"key":"e_1_3_2_1_23_1","volume-title":"A parallel approximation algorithm for mixed packing and covering semidefinite programs. CoRR, abs\/1201.6090","author":"Jain Rahul","year":"2012","unstructured":"Rahul Jain and Penghui Yao . A parallel approximation algorithm for mixed packing and covering semidefinite programs. CoRR, abs\/1201.6090 , 2012 . Rahul Jain and Penghui Yao. A parallel approximation algorithm for mixed packing and covering semidefinite programs. CoRR, abs\/1201.6090, 2012."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556780500065283"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274791"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.016"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0613066"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.17"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.69"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167211"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"e_1_3_2_1_32_1","volume-title":"An o(m\/\u220a^3.5)-cost algorithm for semidefinite programs with diagonal constraints. CoRR, abs\/1903.01859","author":"Lee Yin Tat","year":"2019","unstructured":"Yin Tat Lee and Swati Padmanabhan . An o(m\/\u220a^3.5)-cost algorithm for semidefinite programs with diagonal constraints. CoRR, abs\/1903.01859 , 2019 . Yin Tat Lee and Swati Padmanabhan. An o(m\/\u220a^3.5)-cost algorithm for semidefinite programs with diagonal constraints. CoRR, abs\/1903.01859, 2019."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055477"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.68"},{"key":"e_1_3_2_1_35_1","first-page":"303","volume-title":"Studies in Mathematical Physics","author":"Lieb E. H.","year":"1976","unstructured":"E. H. Lieb and W. E. Thirring . Inequalities for the moments of the eigenvalues of the schrodinger hamiltonian and their relation to sobolev inequalities . Studies in Mathematical Physics , pages 269\u2013 303 , 1976 . E. H. Lieb and W. E. Thirring. Inequalities for the moments of the eigenvalues of the schrodinger hamiltonian and their relation to sobolev inequalities. Studies in Mathematical Physics, pages 269\u2013303, 1976."},{"key":"e_1_3_2_1_36_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016","author":"Mahoney Michael W.","year":"2016","unstructured":"Michael W. Mahoney , Satish Rao , Di Wang , and Peng Zhang . Approximating the solution to mixed packing and covering lps in parallel o(epsilon^3) time. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 , July 11-15, 2016 , Rome, Italy, pages 52:1\u201352:14 , 2016. Michael W. Mahoney, Satish Rao, Di Wang, and Peng Zhang. Approximating the solution to mixed packing and covering lps in parallel o(epsilon^3) time. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 52:1\u201352:14, 2016."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403425629"},{"key":"e_1_3_2_1_38_1","volume-title":"A method of solving a convex programming problem with covergence rate O(1\/k^2)","author":"Nesterov Yu.","year":"1983","unstructured":"Yu. Nesterov . A method of solving a convex programming problem with covergence rate O(1\/k^2) , volume 27 . Soviet Mathematics Doklady , 1983 . Yu. Nesterov. A method of solving a convex programming problem with covergence rate O(1\/k^2), volume 27. Soviet Mathematics Doklady, 1983."},{"key":"e_1_3_2_1_39_1","volume-title":"Self-concordant functions and polynomial-time methods in convex programming","author":"Nesterov Yu.","year":"1989","unstructured":"Yu. Nesterov and A. S. Nemirovskii . Self-concordant functions and polynomial-time methods in convex programming . USSR Academy of Sciences, Central Economic & Mathematic Institute , 1989 . Yu. Nesterov and A. S. Nemirovskii. Self-concordant functions and polynomial-time methods in convex programming. USSR Academy of Sciences, Central Economic & Mathematic Institute, 1989."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214080"},{"key":"e_1_3_2_1_41_1","volume-title":"Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing","author":"Victor","year":"1999","unstructured":"Victor Y. Pan and Zhao Q. Chen. The complexity of the matrix eigenproblem . In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing , May 1-4, 1999 , Atlanta, Georgia, USA, pages 507\u2013516 , 1999. Victor Y. Pan and Zhao Q. Chen. The complexity of the matrix eigenproblem. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA, pages 507\u2013516, 1999."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0718026"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/3219302.3219303"},{"key":"e_1_3_2_1_44_1","volume-title":"Faster and simpler width-independent parallel algorithms for positive semidefinite programming. CoRR, abs\/1201.5135","author":"Peng Richard","year":"2016","unstructured":"Richard Peng , Kanat Tangwongsan , and Peng Zhang . Faster and simpler width-independent parallel algorithms for positive semidefinite programming. CoRR, abs\/1201.5135 , 2016 . Richard Peng, Kanat Tangwongsan, and Peng Zhang. Faster and simpler width-independent parallel algorithms for positive semidefinite programming. CoRR, abs\/1201.5135, 2016."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000065"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1704727"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/1038003"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1705306"},{"key":"e_1_3_2_1_50_1","first-page":"1488","volume-title":"Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems","author":"Manfred","year":"2006","unstructured":"Manfred K. Warmuth and Dima Kuzmin. Randomized PCA algorithms with regret bounds that are logarithmic in the dimension. In Advances in Neural Information Processing Systems 19 , Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems , Vancouver, British Columbia, Canada , December 4-7, 2006 , pages 1481\u2013 1488 , 2006. Manfred K. Warmuth and Dima Kuzmin. Randomized PCA algorithms with regret bounds that are logarithmic in the dimension. In Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, pages 1481\u20131488, 2006."},{"key":"e_1_3_2_1_51_1","volume-title":"Faster parallel solver for positive linear programs via dynamically-bucketed selective coordinate descent. CoRR, abs\/1511.06468","author":"Wang Di","year":"2015","unstructured":"Di Wang , Michael W. Mahoney , Nishanth Mohan , and Satish Rao . Faster parallel solver for positive linear programs via dynamically-bucketed selective coordinate descent. CoRR, abs\/1511.06468 , 2015 . Di Wang, Michael W. Mahoney, Nishanth Mohan, and Satish Rao. Faster parallel solver for positive linear programs via dynamically-bucketed selective coordinate descent. CoRR, abs\/1511.06468, 2015."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959930"},{"key":"e_1_3_2_1_53_1","volume-title":"Nearly linear-time approximation schemes for mixed packing\/covering and facility-location linear programs. CoRR, abs\/1407.3015","author":"Young Neal E.","year":"2014","unstructured":"Neal E. Young . Nearly linear-time approximation schemes for mixed packing\/covering and facility-location linear programs. CoRR, abs\/1407.3015 , 2014 . Neal E. Young. Nearly linear-time approximation schemes for mixed packing\/covering and facility-location linear programs. CoRR, abs\/1407.3015, 2014."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Chicago IL USA","acronym":"STOC '20"},"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.3384338","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384338","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:57Z","timestamp":1750199577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384338"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":53,"alternative-id":["10.1145\/3357713.3384338","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384338","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"}}]}}