Let $k_\epsilon(n)$ be the smallest number of real linear measurements needed by a randomized, oblivious sketch that estimates the nuclear norm of every fixed real $n\times n$ matrix within a factor $1\pm\epsilon$, with probability at least $2/3$. For every fixed $0<\epsilon<1$, the proved result is $$ \frac{n^2}{(\log n)^{A_\epsilon}} \;\le\; k_\epsilon(n) \;\le\; C_\epsilon\frac{n^2\{\log\log(e^e n)\}^2}{\log(e n)} $$ for all sufficiently large $n$, where $A_\epsilon,C_\epsilon$ depend only on $\epsilon$. Previously, the best bounds for general linear sketches were $\Omega(n)$ and the trivial $O(n^2)$ upper bound (Li, Nguyen, Woodruff, 2019). The theorem therefore nearly resolves the open measurement-complexity question left by that work: the displayed lower and upper bounds are tight up to polylogarithmic factors. In particular, the complexity is $n^{2-o(1)}$, and for every fixed $c>0$, $O(n^{2-c})$ measurements are impossible. The upper bound is obtained by a fixed Gaussian sketch whose decoder combines implicit low-rank recovery with moment estimation on a high-stable-rank residual. The lower bound constructs moment-matched spectra, randomizes their singular vectors, and compares every low-dimensional observation through an odd-order tensor estimate and a Fisher-information path argument.
We give a random-bit-efficient construction for the inverse star discrepancy. For every fixed $u\in(0,1)$, $k$-wise independent uniform points $\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N$ with $k=O(d(1+\log(1+N/d)))$ satisfy the Monte Carlo bound $D_N^*(\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N) =O(\sqrt{d/N})$ with probability at least $u$. Consequently, $N=O(d\varepsilon^{-2})$ and $k=O(d(1+\log\varepsilon^{-1}))$ suffice to attain discrepancy at most $\varepsilon$. The proof isolates the finitely many moments required by a chaining argument and gives explicit constants. A random vector-valued polynomial over a finite field realizes the required bounded independence on a grid using $O(d^2(1+\log(1+N/d))\log N)$ random bits, rather than the $\Theta(dN\log(dN))$ bits used by independent grid sampling.
For the $n\times n$ lower-triangular all-ones matrix $Q$, we prove a near-optimal lower bound \[ \gamma_{2,1}(Q) := \inf_{Q=AB} \|A\|_{2\to\infty}\|B\|_{1\to1} = \Omega\!\left( \frac{\log^{3/2}n}{(\log\log n)^{3/2}} \right), \] where the infimum ranges over real factorizations of arbitrary finite inner dimension. This cost is a central parameter in space bounds for factorization-based rank and quantile estimation in turnstile streams and in error bounds for matrix mechanisms for continual counting under pure differential privacy. The proof combines right-sided Haar projections with a scale-dependent numerical-sparsity decomposition of the rows of $B$. At each scale, a rank--Frobenius argument shows that the numerically sparse rows cannot account for all of the required Schatten $2/3$ mass, while a Haar projection estimate bounds the contribution of the remaining rows. Summing these bounds over the dyadic scales yields the result. The proof was obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors verified the proof and made minor revisions.
Honghao Lin, V. Mirrokni, David P. Woodruff· 0 citations
Let $X_1,\ldots,X_N$ be independent random vectors in $\mathbb{R}^n$ with common isotropic log-concave distribution $\mu$ and set $P_{N,n}^{\mu}:=\operatorname{conv}\{\pm X_i:1\leqslant i\leqslant N\}$. Assume that $N/n=\gamma\geqslant \gamma_0$ where $\gamma_0>1$ is an absolute constant. We prove that with probability at least $1-C\gamma\exp(-c n^{1/4})$ every $k$-dimensional subspace $E$ of $(\mathbb{R}^n,\|\cdot\|_{P_{N,n}^{\mu}})$ satisfies $d_{\mathrm{BM}} (E,\ell_\infty^k) \geqslant c\gamma^{-C}k^\alpha$ for every $1\leqslant k\leqslant n$ where $c,C,\alpha>0$ are absolute constants. Consequently, with the same probability, $(\mathbb{R}^n,\|\cdot\|_{P_{N,n}^{\mu}})$ has cotype $q(\gamma)<\infty$ with cotype constant depending only on $\gamma$, in particular the cotype exponent and the cotype constant are independent of $n$ and of $\mu$. The proof adapts the deterministic coefficient scheme of Huang-Tikhomirov replacing the Gaussian estimates in their argument by estimates for isotropic log-concave random matrices. As an application, using the log-concave extension of Gluskin's theorem, we obtain a separable Banach space of finite cotype for which the Banach-Mazur diameter of its $k$-dimensional subspaces is of order $k$ and whose finite-dimensional building blocks are generated by isotropic log-concave random polytopes.
The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean space with distortion at most $1+\varepsilon$. Larsen and Nelson conjectured that the optimal target dimension throughout the full range of the parameters $n,d, \varepsilon$ is \[ \Theta\left(\min\left\{d,n-1,\frac{\log(2+\varepsilon^2n)}{\varepsilon^2}\right\}\right). \] We resolve this conjecture in the affirmative. In fact, we prove the stronger statement that the upper bound is attained by a linear map. The matching lower bound, due to Larsen--Nelson and Alon--Klartag, holds even for nonlinear embeddings.
We prove bounds of order $n^{n/2}e^{O(n)}$ for the expected number of facets of high-dimensional random polytopes. First, let $\mu$ be a non-degenerate compactly supported even probability measure on $\R$ satisfying $\mu([x^\ast-s,x^\ast])\asymp s^\kappa$ near its right endpoint $x^\ast$. For every sufficiently small fixed $\alpha>0$, the convex hull of $N=\lfloor e^{\alpha n}\rfloor$ independent points with law $\mu^{\otimes n}$ has at least $n^{n/2}e^{-C_{\mu,\alpha}n}$ expected facets; this includes all symmetric finite-alphabet distributions. For every full-dimensional log-concave probability measure on $\R^n$, we prove that there exist $T\in[n,2n]$ and $N=\lceil e^Tn^{3/2}\rceil$ for which \[ n^{n/2}e^{-Cn} \leq \mathbb E f_{n-1}(P_N) \leq n^{n/2}e^{Cn}. \] Thus the scale $n^{n/2}$, up to exponential factors, is universal for log-concave measures in this high-dimensional exponential regime. Finally, we construct a symmetric isotropic full-support non-log-concave counterexample with only $(1+o(1))2^n$ expected facets.
We provide a local computation algorithm to approximate the top eigenvector $x \in \mathbb{R}^n$ of a symmetric matrix $A \in \mathbb{R}^{n \times n}$ with entries between $-1$ and $1$, building on the work of Swartworth and Woodruff [SODA 25] who show how to approximate the eigenvalues up to additive-$\varepsilon n$ error using $\tilde{O}(1/\varepsilon^4)$ queries. Our local computation algorithm has a preprocessing complexity of $\tilde{O}(1/\varepsilon^4)$ and per-coordinate query complexity of $\tilde{O}(1/\varepsilon^2)$ for an additive-$\varepsilon n$ approximation whenever {$|\lambda_{\min}(A)| = O(\lambda_{\max}(A))$. When $\lambda_{\min}(A)$ greatly exceeds $\lambda_{\max}(A)$, our complexity degrades to at most $\tilde{O}(1/\varepsilon^{6.\overline{6}})$ in preprocessing and $\tilde{O}(1/\varepsilon^{3.\overline{3}})$ per query. Furthermore, we show a lower bound of $\Omega(n/\varepsilon^2)$ on the total number of queries needed to output an approximately top eigenvector (implying that the per-coordinate query complexity of $\Omega(1/\varepsilon^2)$ is necessary). As an application, we use our algorithm to provide local computation algorithms for the sparsest-cut and max-cut problems in the dense graph model of Goldreich, Goldwasser, Ron [JACM 98]. By accessing the top eigenvectors (of an approximate normalized adjacency), we implement local versions of Cheeger's inequality and Trevisan's algorithm [SICOMP 12] to obtain"square-root-opt"approximations in polynomial time (as opposed to exponential-in-$\text{poly}(1/\varepsilon)$ time which is incurred in Goldreich, Goldwasser, Ron.
