CS Paper Radar

Improving the Constant in the Aharonov--Regev Theorem

Shuhong Gao

cs.CC ·submitted 2026-10-07 01:46 UTC · v1
theory

Abstract

The Aharonov-Regev proof that $\mathrm{GapCVP}_{c\sqrt n}$ lies in $\mathsf{NP}\cap \mathsf{coNP}$ uses a verifier that tests dual lattice vectors; its proof gives $c=100$. We study this verifier through a linear program in which a certificate is modeled as a sample from a probability distribution on the dual lattice. This viewpoint gives an exact analysis of the close-target tests: adding gradient and Hessian checks increases the certified close radius from $σ^{-1}/4$ to $σ^{-1}\sqrt{3/16}$, and higher derivatives cannot improve it within this framework. With Gaussian certificates for far targets, we obtain $$\mathrm{GapCVP}_{c\sqrt n},\ \mathrm{GapSVP}_{c\sqrt n}\in \mathsf{NP} \cap\mathsf{coNP}$$ for every $c>2/(π\sqrt3)\approx0.3676$. An appendix gives a finite-bit implementation of the verifier. We also show that the Gaussian certificate is not always optimal and solve the unbounded-support program exactly for targets of order two, where its value is determined by the spectral capacity of an odd dual coset.

Closest papers

Nearest neighbours by meaning across the whole index.

Three Standard Deviations Suffice While One Does Not

cs.DM math.CO ·2026-09-28 ·Victor Reis, Zhao Song
theory similarity 0.63
Abstract · 15 pages

Spencer's 1985 ``six standard deviations suffice'' theorem shows that every $A \in [-1,1]^{n \times n}$ has a sign vector $x \in \{-1,1\}^n$ with $\|Ax\|_\infty \le 6\sqrt{n}$. We show the upper bound $\sqrt{3\operatorname{arsinh}(10)}\sqrt{n}+4 < 2.9992 \sqrt{n} + 4$ by directly rounding the minimizer of a potential function to a vertex of the cube. We also show that, for every power of two $n \ge 2^{50}$, there exists a matrix $A \in \{-1,1\}^{n \times n}$ such that $\|Ax\|_\infty >1.0000002\sqrt{n}$ for every choice of signs $x \in \{-1,1\}^n$. The construction simply replaces a $2^{-22}$ fraction of the columns of a Hadamard matrix with independent random sign vectors. This is the first improvement over the $\sqrt{n}$ lower bound of Olson and Spencer (1978), which uses a Hadamard matrix.

0.11

Gaussian Difference Dynamics: Breaking the $2^{n/2}$ Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling

cs.DS cs.CR ·2026-11-03 ·Yiming Gao, Xuyuan Han, Honggang Hu
similarity 0.61
Abstract

We give classical randomized algorithms in a word RAM model that break the $2^{n/2}$ barrier for both discrete Gaussian sampling (DGS) and the Shortest Vector Problem (SVP). For every fixed $α>1$, shifted DGS on arbitrary lattices at width $σ\geαη_{1/2}(L)$ takes $$ (3/2)^{n/2+o(n)}\text{ time} \qquad\text{and}\qquad (4/3)^{n/2+o(n)}\text{ space}. $$ These bounds match the Becker--Ducas--Gama--Laarhoven (BDGL) heuristic sieving exponents. At widths at least $3η_{1/2}(L)/2$, the same total cost suffices for an entire batch of $\lfloor(4/3)^{n/2}\rfloor$ samples jointly close to independent target Gaussians. For SVP on arbitrary lattices, our algorithm returns a shortest nonzero vector with high probability in $$ 2^{0.4130n+o(n)}\text{ time} \qquad\text{and}\qquad 2^{0.3138n+o(n)}\text{ space}. $$ As a corollary, we obtain centered DGS at every width with the same exponents, answering a question of Stephens-Davidowitz (SODA 2016). We introduce Gaussian difference dynamics (GDD), a framework for tracking expected counts and pairwise clustering of vectors through repeated differencing. A closed recursion for the first two counting moments controls these quantities relative to a Gaussian reference, without requiring independence within intermediate lists. Accurate moment bounds let us extract a Gaussian sample by weighted selection, while the weaker bounds needed to establish a shortest vector representation allow us to retain more differences. We perform these transitions on thin spherical shells, where the Gaussian rejection weights can be renormalized at subexponential cost. For batch sampling, we combine this geometry with the double rejection technique of Doulgerakis and Laarhoven to control the joint distribution of outputs while reusing vectors.

0.50

A Sharper Explicit Bound on the Subtour-LP Integrality Gap for Metric TSP

cs.DS ·2026-09-28 ·Zhao Song
theory similarity 0.60
Abstract

Karlin, Klein, and Oveis Gharan introduced a randomized better-than-$3/2$ approximation algorithm for metric TSP [KKO21] and subsequently established the corresponding improvement in the integrality gap of the subtour-elimination LP [KKO22], with an explicit constant $\varepsilon>1.00000\cdot10^{-36}$. Gurvits, Klein, and Leake subsequently improved the certified saving to $2.18000\cdot10^{-34}$ [GKL24]. In this paper, we obtain a randomized polynomial-time $(3/2-\varepsilon)$-approximation for every fixed $0<\varepsilon<\varepsilon_\star$, where $\varepsilon_\star>2.78621\cdot10^{-18}$, and consequently the subtour-elimination LP has integrality gap at most $3/2-\varepsilon_\star$. The classical worst-case integrality-gap lower bound is $4/3$ [Wil90].

0.40

Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input

cs.DS math.FAmath.OCmath.PR ·2026-09-14 ·Zhao Song, Lichen Zhang
theory similarity 0.58
Abstract

The Matrix Spencer conjecture asserts that for all symmetric matrices $A_1,\ldots,A_n\in\mathbb{R}^{n\times n}$ with $\|A_i\|\le1$ there are signs $\varepsilon_1,\ldots,\varepsilon_n\in\{-1,1\}$ with $\|\sum_{i=1}^n\varepsilon_iA_i\|=O(\sqrt n)$. We prove it: a signing of discrepancy below $8\sqrt n$ always exists. We also give a randomized algorithm that finds a signing of discrepancy below $12\sqrt n$ with failure probability at most $p$. The algorithm uses $n^{3+o(1)}\operatorname{polylog}(1/p)$ arithmetic operations in the real-arithmetic model. This matches the size $n^3$ of the dense input up to subpolynomial factors. In the other direction, we prove that for every $n$ there are collections of symmetric matrices such that every signing has discrepancy at least $(2-o(1))\sqrt{n}$. We present three different proofs of the matrix Spencer conjecture. The key to every proof is a hereditary small-ball estimate. This is a lower bound on the Gaussian measure of the spectral body $\{x\in \mathbb{R}^n:\|\sum_ix_iA_i\|\le R\}$ that holds for every subfamily of the matrices. The other ingredient turns that Gaussian measure into a partial signing. We give three approaches to obtain such a signing. The first one covers the cube by partially signed faces through Gaussian concentration with a constant $7\cdot10^9$. The second proof replaces the covering by a projection lemma with explicit parameters for a constant $156000$. The third proof turns Gaussian measure into signs by a lossless coding, with no union bound. It proves the estimate at the right radius with smooth spectral barriers and certified coefficients. It gives a constant below $7.88$. For algorithms, the main idea is to project Gaussian points onto a smoothed spectral body. The $n^{3+o(1)}$ time algorithm tracks the Gibbs matrix of that body across coordinate-descent steps with sketched increments and random refreshes.

0.44

Mathematics and Efficiency of Song's CVP Hardness Reduction

cs.CC ·2026-10-29 ·Shuhong Gao
theoryhot direction similarity 0.58
Abstract

Song (2026) proves that, for every fixed $0<ε<1$, the closest codeword problem (CCP) for binary linear codes under Hamming distance is NP-hard to approximate within $N^{1-ε}$, where $N$ is the code length, under deterministic polynomial-time many-one reductions. The code-to-lattice construction gives hardness within $N^{1/2-ε/2}$ for Euclidean CVP, with the same $N$ aslattice rank. This reaches every fixed Euclidean hardness exponent below one half. Aharonov and Regev (2005), with the constant refined by Gao (2026), place GapCVP at factor $cN^{1/2}$ in $\mathrm{NP}\cap\mathrm{coNP}$ for every fixed $c>2/(π\sqrt3)\approx0.3676$. NP-hardness at that scale would imply $\mathrm{NP}=\mathrm{coNP}$. This paper has two goals: to explain Song's theorem and its mathematics for graduate students, and to make the reduction more efficient. The reduction turns satisfiability into a system of quadratic equations and then into CCP for binary linear codes, and recovers assignments from recurrence relations of algebraic moments. We adapt the method to linear codes over any fixed finite field of characteristic $p$. A common recurrence for each block column gives a moment window $L=c_p(κ-1)+1$, where $c_p=\max\{2,p-1\}$ and $κ$ is the rank cutoff. Together with ordinary digit products and flexible sampling, this reduces interpolation degrees and output lengths. For CCP gap $N^{1-ε}$, our explicit schedule gives code length and lattice rank at most $n^{4/ε^2+O(1/ε)}$; Song's prescribed binary schedule gives $n^{8/ε^2+O(1/ε)}$. Here $n$ counts variables in a common quadratic system, equal to the number of original variables plus clauses for 3SAT. These are dimension bounds, not optimality claims or running-time exponents. The limiting hardness exponents remain Song's.

0.30

Fooling Thresholds of Halfspaces

cs.CC ·2026-09-18 ·Minglong Qin, Penghui Yao, Mingnan Zhao, Haigang Zhou
theory similarity 0.57
Abstract · 55 pages, including appendices and references

We initiate the study of constructing explicit pseudorandom generators for thresholds of halfspaces with seed length polylogarithmic in the number of halfspaces. This class of functions lies at the frontier of circuit complexity [CTW26]. We show that the generator designed by O'Donnell, Servedio, and Tan for polytopes [OST22] also fools this broader class. To analyze the generator, we develop a threshold-specific smooth approximation framework based on a Bentkus-type mollifier. We prove derivative bounds for this mollifier and also establish a Boolean anticoncentration theorem for thresholds of halfspaces via a random thinning argument. These ingredients imply that the generator $δ$-fools every $k$-out-of-$m$ threshold of $m$ halfspaces over $\{-1,1\}^n$ with seed length $\widetilde{O}(κ^{6+2\varepsilon}\log^{6+2\varepsilon}\!m\cdotδ^{-(2+2\varepsilon)}\log n)$, for any arbitrarily small constant $\varepsilon>0$, where $κ=\min\{k,m-k+1\}$. The random thinning argument also yields bounds on the noise sensitivity and Gaussian surface area for thresholds of halfspaces, leading to learning algorithms under both the uniform and Gaussian distributions.

0.32

On Complexity of Gaussian Sampling

cs.CC stat.CO ·2026-10-14 ·Huanjian Zhou, Taiji Suzuki
theory similarity 0.57
Abstract · 36 pages

We study the number of exact matrix-vector queries needed to sample a centered $d$-dimensional Gaussian with condition number at most $κ$ to total variation error $\varepsilon$. The best known algorithm uses $O(\min\{d,\sqrtκ\log(\frac{d}{\varepsilon})\})$ queries, while the known lower bounds do not grow as $\varepsilon\to0$ and match this bound only for $κ\le d^{1/5-δ}$ at constant accuracy. We introduce a construction based on a hidden determinant sign and prove a lower bound of $Ω\!\left(\min\left\{d,\sqrtκ\log\left(1+\frac{d}{\sqrtκ\,\varepsilon}\right)\right\}\right)$ uniformly for all $d\ge1$, $κ\ge4$, and $0<\varepsilon\le\tfrac{1}{16}$. This bound matches the known upper bound up to constant factors whenever $κ\le d^{2-δ}$ for fixed $δ\in(0,2)$, or $\varepsilon\le d^{-c}$ for fixed $c>0$. We also extend a recent fixed-spectrum construction with a hidden eigenbasis from $κ=2$ to $2\leκ\le d^{1-δ}$, for any fixed $δ\in(0,1)$. This gives an $Ω_δ(\sqrtκ\log d)$ lower bound at constant accuracy that holds even when the spectrum of the precision matrix is known to the algorithm.

0.13

The sharp SAT/UNSAT phase transition in random ellipsoid fitting

cs.DS math.PRcond-mat.dis-nnmath.ST+1 ·2026-08-10 ·Theodor Misiakiewicz, Garrett G. Wen
theory similarity 0.57
Abstract

Let $x_1,\ldots,x_n$ be independent standard Gaussian vectors in $\mathbb{R}^d$. An \emph{ellipsoid fit} is a matrix $S \succeq 0$ such that $x_i^\top S x_i =d$ for every $i$, so that all the points lie on the boundary of the centered ellipsoid $\{ x : x^\top S x = d\}$. Saunderson, Parrilo and Willsky conjectured that, as $n,d \to \infty$, this semidefinite feasibility problem undergoes a sharp transition at $n \sim d^2/4$. We prove this conjecture. If $\lim \sup n/d^2 = α^* <1/4$, then, with probability tending to one, an ellipsoid fit exists; moreover, one can choose $S$ with all eigenvalues in a fixed interval $[λ_- , λ_+] \subset (0,\infty)$ depending only on $α^*$. Conversely, if $\lim \inf n/d^2 > 1/4$, then, with probability tending to one, no ellipsoid fit exists, without any spectral restriction. Our proof builds on the Gaussian-equivalence framework developed by Bandeira and Maillard (2025) and closes the two gaps left open in their work: establishing exact fitting and removing the operator-norm constraint. On the satisfiable side, the new ingredients are a head-tail decomposition of the dual vector, exact correction of the sparse head constraints, and a Gaussian comparison principle for the low-influence tail. On the unsatisfiable side, we split a candidate into a low-rank spectral head and a Schatten-3 diffuse bulk, Gaussianize the bulk conditionally on the head, and apply a projected Gordon escape argument. The threshold is governed by the statistical dimension $d(d+1)/4$ of the positive semidefinite cone.

0.32