{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T22:58:04Z","timestamp":1781218684950,"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-501."},{"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 [math.OC]"},{"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 Advances in Neural Information Processing Systems 33 (NeurIPS)."},{"key":"e_1_3_2_1_7_1","volume-title":"34th Annual Conference on Computational Learning Theory (COLT).","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 34th Annual Conference on Computational Learning Theory (COLT)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.130"},{"key":"e_1_3_2_1_9_1","unstructured":"Yair Carmon Yujia Jin Aaron Sidford and Kevin Tian. 2019. Variance Reduction for Matrix Games. In Advances in Neural Information Processing Systems 32 (NeurIPS)."},{"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","volume-title":"22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Daskalakis Constantinos","year":"2011","unstructured":"Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. 2011. Nearoptimal no-regret algorithms for zero-sum games. In 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"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","doi-asserted-by":"crossref","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 Advances in Neural Information Processing Systems 37 (NeurIPS).","DOI":"10.52202\/075280-0586"},{"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- 720."},{"key":"e_1_3_2_1_18_1","volume-title":"Solving Zero-Sum Games with Fewer Matrix-Vector Products. In 66th Annual IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Karmarkar Ishani","unstructured":"Ishani Karmarkar, Liam O'Carroll, and Aaron Sidford. [n. d.]. Solving Zero-Sum Games with Fewer Matrix-Vector Products. In 66th Annual IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_19_1","volume-title":"The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria. In 38th Annual Conference on Computational Learning Theory (COLT).","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 38th Annual Conference on Computational Learning Theory (COLT)."},{"key":"e_1_3_2_1_20_1","unstructured":"Guy Kornowski and Ohad Shamir. 2025. The Oracle Complexity of Simplexbased 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's thesis","author":"Makur Anuran","unstructured":"Anuran Makur. 2015. A Study of Local Approximations in Information Theory. Master's 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: Primaldual 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: Primaldual coupled variance reduction for faster distributionally robust optimization. Advances in Neural Information Processing Systems 37 (2024), 134770-134825.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_25_1","volume-title":"Min-Max Optimization with Dual-Linear Coupling. arXiv preprint arXiv:2507.06328","author":"Mehta Ronak","year":"2025","unstructured":"Ronak Mehta, Jelena Diakonikolas, and Zaid Harchaoui. 2025. Min-Max Optimization with Dual-Linear Coupling. arXiv preprint arXiv:2507.06328 (2025)."},{"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 (01","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 (01 Mar 2007), 319-344."},{"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-1019."},{"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) (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) (Proceedings of Machine Learning Research, Vol. 32), Eric P. Xing and Tony Jebara (Eds.). PMLR, 1593-1601."},{"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 (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 (Proceedings of Machine Learning Research, Vol. 32), Eric P. Xing and Tony Jebara (Eds.). PMLR, Beijing, China, 1827-1835."}],"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,11]],"date-time":"2026-06-11T22:33:18Z","timestamp":1781217198000},"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"}}]}}