{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:18Z","timestamp":1781031438467,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1955039"],"award-info":[{"award-number":["CCF-1955039"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["CCF-1955039"],"award-info":[{"award-number":["CCF-1955039"]}]},{"name":"National Science Foundation","award":["CCF1955039"],"award-info":[{"award-number":["CCF1955039"]}]},{"DOI":"10.13039\/100000001","name":"PayPal","doi-asserted-by":"publisher","award":["PayPal Research Award"],"award-info":[{"award-number":["PayPal Research Award"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Microsoft","award":["Microsoft Research Faculty Fellowship"],"award-info":[{"award-number":["Microsoft Research Faculty Fellowship"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800880","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1728-1738","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Solving Matrix Games with Near-Optimal Matvec Complexity"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-9126-8967","authenticated-orcid":false,"given":"Ishani","family":"Karmarkar","sequence":"first","affiliation":[{"name":"Stanford University, Computational and Mathematical Engineering, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-0596-0930","authenticated-orcid":false,"given":"Liam","family":"O'Carroll","sequence":"additional","affiliation":[{"name":"Stanford University, Computer Science, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2675-7610","authenticated-orcid":false,"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[{"name":"Stanford University, Computer Science, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-012-0328-8"},{"key":"e_1_3_2_1_2_1","series-title":"SIAM journal on control and optimization, 43, 2","volume-title":"Hessian Riemannian gradient flows in convex programming","author":"Alvarez Felipe","year":"2004","unstructured":"Felipe Alvarez, J\u00e9r\u00f4me Bolte, and Olivier Brahic. 2004. Hessian Riemannian gradient flows in convex programming. SIAM journal on control and optimization, 43, 2 (2004), 477\u2013501."},{"key":"e_1_3_2_1_3_1","volume-title":"Near-optimal Approximate Discrete and Continuous Submodular Function Minimization. In ACM-SIAM Symposium on Discrete Algorithms.","author":"Axelrod Brian","year":"2019","unstructured":"Brian Axelrod, Yang P. Liu, and Aaron Sidford. 2019. Near-optimal Approximate Discrete and Continuous Submodular Function Minimization. In ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_3_2_1_4_1","unstructured":"Fran\u00e7ois Bachoc Tommaso Cesari Roberto Colomboni and Andrea Paudice. 2022. A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex Optimization. arxiv:2208.06720."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(02)00231-6"},{"key":"e_1_3_2_1_6_1","volume-title":"Aaron Sidford, and Kevin Tian.","author":"Carmon Yair","year":"2020","unstructured":"Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. 2020. Acceleration with a ball optimization oracle. In 2020."},{"key":"e_1_3_2_1_7_1","volume-title":"Thinking inside the ball: Near-optimal minimization of the maximal loss. In","author":"Carmon Yair","year":"2021","unstructured":"Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. 2021. Thinking inside the ball: Near-optimal minimization of the maximal loss. In 2021."},{"key":"e_1_3_2_1_8_1","volume-title":"A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions. In","author":"Carmon Yair","year":"2024","unstructured":"Yair Carmon, Arun Jambulapati, Yujia Jin, and Aaron Sidford. 2024. A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions. In 2024."},{"key":"e_1_3_2_1_9_1","volume-title":"Variance Reduction for Matrix Games. In","author":"Carmon Yair","year":"2019","unstructured":"Yair Carmon, Yujia Jin, Aaron Sidford, and Kevin Tian. 2019. Variance Reduction for Matrix Games. In 2019."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00035"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Kenneth L Clarkson Elad Hazan and David P Woodruff. 2012. Sublinear optimization for machine learning. In Journal of the ACM (JACM).","DOI":"10.1145\/2371656.2371658"},{"key":"e_1_3_2_1_12_1","volume-title":"Linear Programming and Extensions","author":"Dantzig G. B.","unstructured":"G. B. Dantzig. 1953. Linear Programming and Extensions. Princeton University Press, Princeton, NJ."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.21"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Yoav Freund and Robert E Schapire. 1999. Adaptive game playing using multiplicative weights. In Games and Economic Behavior.","DOI":"10.1006\/game.1999.0738"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Michael D Grigoriadis and Leonid G Khachiyan. 1995. A sublinear-time randomized approximation algorithm for matrix games. In Operations Research Letters.","DOI":"10.1016\/0167-6377(95)00032-0"},{"key":"e_1_3_2_1_16_1","volume-title":"Towards characterizing the first-order query complexity of learning (approximate) nash equilibria in zero-sum matrix games. In","author":"Hadiji H\u00e9di","year":"2024","unstructured":"H\u00e9di Hadiji, Sarah Sachs, Tim van Erven, and Wouter M Koolen. 2024. Towards characterizing the first-order query complexity of learning (approximate) nash equilibria in zero-sum matrix games. In 2024."},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the International Conference on Algorithmic Learning Theory (Proceedings of Machine Learning Research","volume":"720","author":"Joulani Pooria","year":"2017","unstructured":"Pooria Joulani, Andr\u00e1s Gy\u00f6rgy, and Csaba Szepesv\u00e1ri. 2017. A modular analysis of adaptive (non-)convex optimization: Optimism, composite objectives, and variational bounds. In Proceedings of the International Conference on Algorithmic Learning Theory (Proceedings of Machine Learning Research, Vol. 76). PMLR, 681\u2013720."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS63196.2025.00125"},{"key":"e_1_3_2_1_19_1","volume-title":"The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria. In","author":"Kornowski Guy","year":"2025","unstructured":"Guy Kornowski and Ohad Shamir. 2025. The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria. In 2025."},{"key":"e_1_3_2_1_20_1","unstructured":"Guy Kornowski and Ohad Shamir. 2025. The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria. In arXiv preprint 2412.06990 [v3]."},{"key":"e_1_3_2_1_21_1","volume-title":"A Study of Local Approximations in Information Theory. Master\u2019s thesis","author":"Makur Anuran","unstructured":"Anuran Makur. 2015. A Study of Local Approximations in Information Theory. Master\u2019s thesis. Massachusetts Institute of Technology. Cambridge, MA. Submitted to the Department of Electrical Engineering and Computer Science"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1051\/m2an\/197004R301541"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Warren S McCulloch and Walter Pitts. 1943. A logical calculus of the ideas immanent in nervous activity. In The bulletin of mathematical biophysics.","DOI":"10.1007\/BF02478259"},{"key":"e_1_3_2_1_24_1","first-page":"134770","article-title":"Drago: Primal-dual coupled variance reduction for faster distributionally robust optimization","volume":"37","author":"Mehta Ronak","year":"2024","unstructured":"Ronak Mehta, Jelena Diakonikolas, and Zaid Harchaoui. 2024. Drago: Primal-dual coupled variance reduction for faster distributionally robust optimization. Advances in Neural Information Processing Systems, 37 (2024), 134770\u2013134825.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_25_1","unstructured":"Ronak Mehta Jelena Diakonikolas and Zaid Harchaoui. 2025. Min-Max Optimization with Dual-Linear Coupling. arXiv preprint arXiv:2507.06328."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/110833786"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403425629"},{"key":"e_1_3_2_1_28_1","volume-title":"Problem complexity and method efficiency in optimization","author":"Nemirovskij Arkadij Semenovi\u010d","unstructured":"Arkadij Semenovi\u010d Nemirovskij and David Borisovich Yudin. 1983. Problem complexity and method efficiency in optimization. In Wiley-Interscience."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Yu Nesterov. 2005. Smooth minimization of non-smooth functions. In Mathematical programming.","DOI":"10.1007\/s10107-004-0552-5"},{"key":"e_1_3_2_1_30_1","volume-title":"Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109, 2","author":"Nesterov Yurii","year":"2007","unstructured":"Yurii Nesterov. 2007. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109, 2 (2007), 01 Mar, 319\u2013344."},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the 26th Annual Conference on Learning Theory (Proceedings of Machine Learning Research","volume":"1019","author":"Rakhlin A.","unstructured":"A. Rakhlin and K. Sridharan. 2013. Online learning with predictable sequences. In Proceedings of the 26th Annual Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 30). PMLR, 993\u20131019."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0314056"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Frank Rosenblatt. 1958. The perceptron: a probabilistic model for information storage and organization in the brain.. In Psychological review.","DOI":"10.1037\/h0042519"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000018"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2621980"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/110848955"},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings of the 31st International Conference on Machine Learning (ICML), Eric P. Xing and Tony Jebara (Eds.) (Proceedings of Machine Learning Research","volume":"1601","author":"Steinhardt Jacob","year":"2014","unstructured":"Jacob Steinhardt and Percy Liang. 2014. Adaptivity and Optimism: An Improved Exponentiated Gradient Algorithm. In Proceedings of the 31st International Conference on Machine Learning (ICML), Eric P. Xing and Tony Jebara (Eds.) (Proceedings of Machine Learning Research, Vol. 32). PMLR, 1593\u20131601."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448847"},{"key":"e_1_3_2_1_39_1","volume-title":"The Eleventh International Conference on Learning Representations.","author":"Wang Guanghui","year":"2023","unstructured":"Guanghui Wang, Rafael Hanashiro, Etash Kumar Guha, and Jacob Abernethy. 2023. On accelerated perceptrons and beyond. In The Eleventh International Conference on Learning Representations."},{"key":"e_1_3_2_1_40_1","volume-title":"Proceedings of the 31st International Conference on Machine Learning, Eric P. Xing and Tony Jebara (Eds.) (Proceedings of Machine Learning Research","volume":"1835","author":"Yu Adams Wei","year":"2014","unstructured":"Adams Wei Yu, Fatma Kilinc-Karzan, and Jaime Carbonell. 2014. Saddle Points and Accelerated Perceptron Algorithms. In Proceedings of the 31st International Conference on Machine Learning, Eric P. Xing and Tony Jebara (Eds.) (Proceedings of Machine Learning Research, Vol. 32). PMLR, Beijing, China. 1827\u20131835."}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800880","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800880","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:00:29Z","timestamp":1781028029000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800880"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":40,"alternative-id":["10.1145\/3798129.3800880","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800880","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}