We study the fundamental classification problem of computing a separating hyperplane for a binary-labeled dataset of size $n$ with normalized $d$-dimensional features. Letting $\Phi \in \mathbb{R}^{n \times d}$ denote the feature matrix and $\gamma$ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in $\tilde{O}(\gamma^{-2/3}\, \operatorname{nnz}(\Phi) + \gamma^{-2(\omega+1)/3})$-sequential running time (work), $\tilde{O}(\gamma^{-2/3})$-parallel (computational) depth, and accesses $\Phi$ only through $\tilde{O}(\gamma^{-2/3})$-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a $\tilde{O}(\gamma^{-2/3}\, \operatorname{nnz}(\Phi) + \gamma^{-2})$-sequential running time that uses $\tilde{O}(\gamma^{-2/3})$-matvecs to $\Phi$, but achieves only $\tilde{O}(\gamma^{-4/3})$-parallel depth. Both algorithms match the near-optimal deterministic matvec complexity recently established by Kornowski and Shamir [2025], Karmarkar et al. [2026] and achieve improved sequential runtime and parallel depth, albeit at the expense of using randomness.

We study the problem of computing an є-approximate Nash equilibrium of a two-player, bilinear game with a bounded payoff matrix A ∈ ℝm × n, when the players’ strategies are constrained to lie in simple sets. We provide algorithms which solve this problem in Õ(є−2/3) matrix-vector multiplies (matvecs) in two well-studied cases: ℓ1-ℓ1 (or zero-sum) games, where the players’ strategies are both in the probability simplex, and ℓ2-ℓ1 games (encompassing hard-margin SVMs), where the players’ strategies are in the unit Euclidean ball and probability simplex respectively. These results improve upon the previous state-of-the-art complexities of Õ(є−8/9) for ℓ1-ℓ1 and Õ(є−7/9) for ℓ2-ℓ1 due to [KOS ’25]. In both settings our results are nearly-optimal as they match lower bounds of [KS ’25] up to polylogarithmic factors.

In this paper we consider the problem of computing an $\epsilon$-approximate Nash Equilibrium of a zerosum game in a payoff matrix $A \in \mathbb{R}^{m \times n}$ with $O(1)$-bounded entries given access to a matrix-vector product oracle for A and its transpose $A^{\top}$. We provide a deterministic algorithm that solves the problem using $\tilde{O}\left(\epsilon^{-8 / 9}\right)$-oracle queries, where $\tilde{O}(\cdot)$ hides factors polylogarithmic in m, n, and $\epsilon^{-1}$. Our result improves upon the state-of-the-art query complexity of $\tilde{O}\left(\epsilon^{-1}\right)$ established by [Nemirovski, 2004] and [Nesterov, 2005]. We obtain this result through a general framework that yields improved deterministic query complexities for solving a broader class of minimax optimization problems which includes computing a linear classifier (hard-margin support vector machine) as well as linear regression.11This paper is an extended abstract. The full paper can be accessed at https://arxiv.org/abs/2509.04426.

We provide a general method to convert a "primal" black-box algorithm for solving regularized convex-concave minimax optimization problems into an algorithm for solving the associated dual maximin optimization problem. Our method adds recursive regularization over a logarithmic number of rounds where each round consists of an approximate regularized primal optimization followed by the computation of a dual best response. We apply this result to obtain new state-of-the-art runtimes for solving matrix games in specific parameter regimes, obtain improved query complexity for solving the dual of the CVaR distributionally robust optimization (DRO) problem, and recover the optimal query complexity for finding a stationary point of a convex function.

We consider the problem of minimizing a $d$-dimensional Lipschitz convex function using a stochastic gradient oracle. We introduce and motivate a setting where the noise of the stochastic gradient is isotropic in that it is bounded in every direction with high probability. We then develop an algorithm for this setting which improves upon prior results by a factor of $d$ in certain regimes, and as a corollary, achieves a new state-of-the-art complexity for sub-exponential noise. We give matching lower bounds (up to polylogarithmic factors) for both results. Additionally, we develop an efficient quantum isotropifier, a quantum algorithm which converts a variance-bounded quantum sampling oracle into one that outputs an unbiased estimate with isotropic error. Combining our results, we obtain improved dimension-dependent rates for quantum stochastic convex optimization.

The most widely used technique for solving large-scale semidefinite programs (SDPs) in practice is the non-convex Burer-Monteiro method, which explicitly maintains a low-rank SDP solution for memory efficiency. There has been much recent interest in obtaining a better theoretical understanding of the Burer-Monteiro method. When the maximum allowed rank $p$ of the SDP solution is above the Barvinok-Pataki bound (where a globally optimal solution of rank at most \(p\) is guaranteed to exist), a recent line of work established convergence to a global optimum for generic or smoothed instances of the problem. However, it was open whether there even exists an instance in this regime where the Burer-Monteiro method fails. We prove that the Burer-Monteiro method can fail for the Max-Cut SDP on $n$ vertices when the rank is above the Barvinok-Pataki bound ($p \ge \sqrt{2n}$). We provide a family of instances that have spurious local minima even when the rank $p = n/2$. Combined with existing guarantees, this settles the question of the existence of spurious local minima for the Max-Cut formulation in all ranges of the rank and justifies the use of beyond worst-case paradigms like smoothed analysis to obtain guarantees for the Burer-Monteiro method.

We study the degree of nonhomogeneous lattice ideals over arbitrary fields, and give formulas to compute the degree in terms of the torsion of certain factor groups of $\mathbb{Z}^s$ and in terms of relative volumes of lattice polytopes. We also study primary decompositions of lattice ideals over an arbitrary field using the Eisenbud--Sturmfels theory of binomial ideals over algebraically closed fields. We then use these results to study certain families of integer matrices (positive critical binomial (PCB), generalized positive critical binomial (GPCB), critical binomial (CB), and generalized critical binomial (GCB) matrices) and the algebra of their corresponding matrix ideals. In particular, the family of GPCB matrices is shown to be closed under transposition, and previous results for PCB ideals are extended to GPCB ideals. Then, more particularly, we give some applications to the theory of $1$-dimensional binomial ideals. If $G$ is a connected graph, we show as a further application that the order of its sandpile group is the degree of the Laplacian ideal and the degree of the toppling ideal. We also use our earlier results to give a structure theorem for graded lattice ideals of dimension $1$ in $3$ variables and for homogeneous lattices in $\mathbb{Z}^3$ in terms of CB ideals and CB matrices, respectively, thus complementing a well-known theorem of Herzog on the toric ideal of a monomial space curve.