In this note, we provide a short and direct proof that approximately solving $Ax=b$ to relative error $\varepsilon$, where $A$ has condition number $\kappa$ and unrestricted dimension, requires $\Omega(\kappa\log(1/\varepsilon))$ matrix-vector multiplications in the worst case, even for randomized algorithms. This essentially recovers the lower bound of Derezi\'nski, Epperly and Meyer [2026] for this setting, whose elegant and more general approach inspired us to seek a short direct proof. A straightforward reduction implies the classical $\Omega(\sqrt{\kappa}\log(1/\varepsilon))$ lower bound for optimizing strongly convex quadratic functions, applicable to randomized algorithms.
We give optimal bounds, up to polylogarithmic factors, for rounding convex bodies to near-isotropic position. A convex body $B(0,r)\subseteq K\subseteq B(0,R)$ in $\R^n$ can be rounded using $\Ot(n^3)$ membership queries; the upper bound extends to logconcave distributions. We prove a matching $\Omegat(n^3)$ lower boun...
Yang P. Liu, Richard Peng, Alicia Stepin et al.· 1 citation
We study the query complexity of optimization with exact scalar-value information. For globally $L$-smooth convex functions on $\mathbb R^d$ with a minimizer in a Euclidean ball of radius $R$, we prove the lower bound $\Omega(d\min\{d,\sqrt{LR^2/\varepsilon}\})$ for adaptive randomized algorithms in the stated accuracy...
Y. Dorn, D. Dvinskikh, Т. В. Логінов et al.· 0 citations
We study gradient descent with predetermined nonnegative stepsizes on smooth strongly convex functions. Let $p_{\mathrm{sil}}=\log_2(1+\sqrt2)$ and $\kappa$ be the condition number. We prove the iteration lower bound $\Omega\left(\kappa^{\frac{1}{p_{\mathrm{sil}}}-o(1)}\log\frac1\delta\right)$ for both relative squared...
We prove that, over any field, the bilinear complexity of multiplying a $3\times 2$ matrix by a $2\times m$ matrix is strictly greater than $24m/5$. In particular, every exact bilinear algorithm for multiplying a $3\times 2$ matrix by a $2\times 5$ matrix requires at least $25$ multiplications. Together with the Hopcro...
Askar Tsyganov, Uliana Parkina, S. Samsonov et al.· 0 citations
We prove an $\Omega(n^2)$ lower bound on the determinantal complexity of the power sum polynomial $\sum_{i=1}^n x_i^n$ over the field of complex numbers. A similar result was claimed in a recent paper of Sheshadri (arXiv:2606.13628), via an AI-assisted and AI-written proof. Assuming its correctness, this was the first...
We prove a joint stochastic zeroth-order lower bound for Goldstein stationarity on a Euclidean query ball, even when the ball is guaranteed to contain a stationary point. In dimension $d$, let $f=\mathbb{E}[F(\cdot;\xi)]$, assume $\mathbb{E}[\operatorname{Lip}(F(\cdot;\xi))^2]\le L_0^2$, and bound the initial objective...
