This work eliminates the residual-stage $O(d)$-bit payload and reduces the leading upper-bound constant by a factor of approximately $5.93$ compared with the two-stage construction of Feng et al.
Abstract
Quantizing high-dimensional vectors is fundamental to similarity search, distributed learning, and model compression. Feng, Indyk, Kapralov, Krachun, and Prokhorov established sharp guarantees for an unbiased dithered quantizer based on a randomized Hadamard transform [FIK+26]. Their $1/d$-scale inner-product estimator, however, uses a second randomized transform and residual quantization, increasing both communication and the leading constant in the proved bound. We show that this extra stage is unnecessary: pairwise-independent dithers across Hadamard coordinates suffice. The resulting unbiased single-stage estimator uses $b$ bits per coordinate and achieves \[ \mathbb{E}\!\left[ \left|\left\langle y,\widehat{x}-x\right\rangle\right|^2 \right] \leq \left(\frac{3\pi\sqrt{3}}{2}+o(1)\right) \frac{\lVert y\rVert_2^2}{d\,4^b}, \] as $b\to\infty$, with a dimension-free $o(1)$ term uniform over unit inputs and fixed queries. Compared with the two-stage construction of Feng et al., it eliminates the residual-stage $O(d)$-bit payload and reduces the leading upper-bound constant by a factor of approximately $5.93$. The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation.
We develop a column-wise chi-squared geometry for discrete memoryless channels (DMCs) yielding tight, logarithm-free bounds on mutual information, channel dispersion, and finite-blocklength coding rates without evaluating logarithms of the channel matrix. The key parameter is~\(\eta\)---the worst-case relative deviation of a transition probability from its output marginal, which is small precisely when the channel is close to the fully noisy channel $t_{ij}=s_j$. We prove three main results: (1) a third-order ratio expansion showing \(I(X;Y)/\chi^2(X;Y)\to 1/2\) as \(\eta\to 0\) with an \(O(\eta)\) skewness correction; (2) a two-sided dispersion equivalence bounding \(V(X;Y)\) above and below by \(\chi^2(X;Y)\) with explicit constants \(c_{\pm}(\eta)\to 1\); and (3) a certified robust design rate \(R_{\mathrm{cert}}(n,\varepsilon)\) with total certification gap \(O(\eta)+O(\eta/\sqrt{n})+O(\log n/n)\). The certified bounds on \(I\) and \(V\) require only addition, multiplication, division, and square roots; the final rate also uses \(Q^{-1}(\varepsilon)\).
H. Tavakoli, Thinh Nguyen, Bella Bose· 0 citations
A randomized fully non-adaptive protocol is constructed that fixes all queries before observing the data and matches the optimal adaptive sample complexity, giving a negative answer to the COLT 2026 open problem asking whether interaction is necessary for order-optimal one-bit mean estimation.
Achieving local differential privacy in distributed optimization while maintaining low communication cost remains challenging. Existing vector quantization methods, such as vqSGD, use high-dimensional geometric constructions but incur unfavorable dimension-dependent variance. In this work, we propose Subsampled Stochastic TurboQuant (SSTQ), a framework that combines overcomplete equal-norm tight frames, coordinate subsampling, and privacy-aware one-dimensional quantization. SSTQ includes two variants: a Flat Randomized Response version and a Metric-Aware Laplace version, the latter being better suited to higher codebook bit-width regimes. We show that SSTQ achieves optimal mean squared error scaling while using only $\lceil \log_2 N \rceil + b$ bits per client, where $N = \Theta(d)$ is the frame size. We also derive a surrogate privacy-aware codebook objective that reduces the codebook-dependent MSE scaling from $O(4^b)$ to $O(2^b)$. Finally, we empirically evaluate SSTQ against established baselines on federated learning tasks using CIFAR-10 and Fashion-MNIST, demonstrating favorable utility and communication efficiency. Some of the analytical derivations were first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified those derivations and edited them for clarity of presentation.
Adel Javanmard, David P. Woodruff, V. Mirrokni· 0 citations
A universal, sample-optimal convergence theorem for the original BIHT algorithm is proved and a scalar lower bound is proved showing that any nontrivial corruption pattern, even one that involves only one flipped sign together with one clean sign, forces the iterates to oscillate indefinitely.
Randomized sketch-and-solve algorithms accelerate overconstrained $\ell_2$ regression by replacing the input with a smaller problem. Standard subspace embeddings guarantee that the cost of the regression is nearly preserved, but coordinate-wise accuracy of the solution is more delicate: we want the solution vector itself to be close to the optimal solution in $\ell_\infty$ norm. In particular, we want to find a vector $x'\in \mathbb{R}^d$ such that $\|x'-x^*\|_\infty\leq \frac{\epsilon}{\sqrt d}\cdot \|Ax^\star-b\|_2\cdot \|A^\dagger\|_{\rm op}$. Price, Song and Woodruff initiated the study of this problem and showed that the subsampled randomized Hadamard transform (SRHT) with $O(\epsilon^{-2} d^{1+\Theta(\sqrt{\log\log n/\log d})})$ rows achieves this guarantee. A subsequent work of Song, Ye, Yin and Zhang claimed to improve the row count to $O(\epsilon^{-2}d\log^3 n)$. Unfortunately, their proof relies on an independence assumption that does not hold in general, and we exhibit an explicit instance on which it fails. To achieve a truly nearly-linear-in-$d$ row count, we introduce a new fast, dense randomized transform, which combines a randomized Hadamard flattening, a random permutation, and balanced, disjoint Gaussian pooling. Conditioned on the Hadamard-and-permutation stage, the sketched problem becomes an exact Gaussian regression in which the noise is independent of the entire sketched design; this conditional independence is exactly what the earlier argument was missing. Our sketch yields the $\ell_\infty$ guarantee with $m=O(\epsilon^{-2}d\log d)$ rows, uses one Hadamard pass with a padded internal dimension $N=\widetilde{O}(n+\epsilon^{-2}d^3)$, and is efficient to apply: the sketched pair $(SA, Sb)$ can be computed in $O(Nd\log N)=\widetilde{O}(nd+\epsilon^{-2}d^4)$ time.
We give an algorithm which, given $n = O(d^2 \cdot (\log\log(d)/\log(d))^2)$ copies of $\rho$, estimates the eigenvalues of $\rho$ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the $\Theta(d^2)$ needed to run full state tomography. This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm, which uses $n = \Theta(d^2)$ copies, thereby resolving a question raised by Keyl and Werner in 2001 and refuting a 2016 conjecture of Wright. Our main technical tool is a new tomography guarantee, where the error of tomography in a particular direction $|w\rangle$ scales with $\langle w | \rho |w\rangle$ for all directions simultaneously. From this stronger"relative-error"bound, we recover better algorithms for principal component analysis in Bures distance and tomography in $\chi^2$-divergence as corollaries.
Angelos Pelecanos, Jack Spilecki, Ewin Tang et al.· 5 citations· ⚡3
