CS Paper Radar

A Short Note on Algorithms For The Noisy $k$-XOR Problem

Kiril Bangachev

cs.DS cs.CCmath.ST ·submitted 2026-10-19 18:41 UTC · v1

Abstract

This mostly expository note studies the sample-noise regimes in which the testing problem for noisy $k$-XOR in dimension $n$ can be efficiently solved. Concretely, we ask what pairs $(β, δ)$ admit algorithms running in time $n^{O(k)}$ where $m = n^β, β\in [0,k]$ is the number of samples and $\mathsf{Bern}(n^{-δ}),δ\in (0,+\infty)$ is the noise distribution. The current state-of-the-art algorithms are: I. A folklore algorithm when $β> 1, δ>1$ based on Gaussian elimination; II. A folklore algorithm when $β\ge k/2$ based on the birthday paradox; III. A recent algorithm in the regime $β> δ+ k(1-δ), δ\in (0,1)$ based on a reduction to the first algorithm [DJ24,CSZ24]. IV. Extending [AF09], we strictly improve the last regime to $β> δ+ (k-1)(1-δ), δ\in (0,1).$ These algorithms correspond to efficiently finding short cycles in uniform hypergraphs and can be equivalently phrased as algorithmic Moore bounds.

Closest papers

Nearest neighbours by meaning across the whole index.

Provably Subexponential Algorithms for Bounded-Error LWE with Few Samples

cs.CR ·2026-10-09 ·Haoxing Lin, Prashant Nalini Vasudevan
similarity 0.62
Abstract

We show that a variant of the Wagner/BKW-style algorithm for LWE of Kirchner and Fouque [KF15] solves decision and search LWE with secrets of size $n$ over prime moduli $q=n^{κ+o(1)}$, for any fixed $κ>0$, with errors bounded by $\exp((\ln n)^{o(1)})$, in time $2^{O(n/\ln\ln n)}$ given $n+O(n/\ln\ln n)$ original samples. Further, if each coordinate of the secret is also bounded by $\exp((\ln n)^{o(1)})$, the same time bound holds with errors bounded by $n^{o(1)}$ and only $O(n/\ln\ln q)$ samples. Earlier, it was known that Kirchner and Fouque's algorithm could solve LWE with these parameters in subexponential time with a much larger number of samples $m = Ω(n\log{n})$ [HKM18]. Ducas et al. [DEL25] showed that an adaptation of this algorithm could solve the corresponding dual, the $\mathrm{SIS}^{\infty}$ problem, with a suitable norm bound $q/\operatorname{polylog}(n)$ and $m=n+ω(n/\ln\ln n)$ variables in subexponential time. Whereas their analysis involves interpreting the algorithm in terms of chains of lattices, our approach is quite elementary and is based on bounding the lower moments of a Fourier statistic.

0.30

Optimal Last-Iterate Bounds for Nonexpansive Stochastic Approximation

cs.LG math.OCeess.SY ·2026-11-10 ·Ramanan Tamizholi, Siddharth Chandak, Rahul Singh
similarity 0.60
Abstract · 23 pages

We establish last-iterate mean-square residual bounds for nonexpansive stochastic approximation (SA), or stochastic Krasnoselskii-Mann (KM) iterations. In particular, we consider fixed-point mappings that are nonexpansive with respect to the Euclidean norm, and focus on polynomially decaying stepsizes. We study three conditions on the conditional second moment of the noise, and obtain bounds that are optimal up to logarithmic factors in each case. When it scales linearly with the squared residual, the best rate is $O(1/k^{1-ε})$ for any $ε>0$. In this case, for all considered stepsizes, our bounds match those of the noiseless KM iteration. When it is bounded by a constant, the best rate is $O(\log^2 k/\sqrt{k})$. When it scales affinely with the squared norm of the iterate, the best rate is $O(1/k^{1/2-ε})$, and the mean-square residual can diverge if the stepsizes are not square-summable. Thus, unlike for contractive SA, square-summable stepsizes are necessary for nonexpansive SA. We demonstrate how various algorithms with cocoercive maps, such as stochastic gradient descent, linear SA, and learning in cocoercive games, fit into our framework, and how the different noise conditions arise in each of them.

0.11

Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli

cs.CR ·2026-10-09 ·Andrej Bogdanov, Kel Zin Tan, Prashant Nalini Vasudevan
published similarity 0.59
Abstract

The Noisy Linear Equations problem involves finding the solution to a random linear system over a finite field given noisy evaluations. This is a generalisation of various learning problems widely used in cryptography, including Learning with Errors (LWE), Learning with Rounding (LWR), and Learning Parity with Noise (LPN). We present a new sample-preserving search-to-decision reduction for Noisy Linear Equations that has complexity $\mathrm{poly}(n,m,\log q, q/σ)$, where $n$ is the dimension of the secret, $m$ is the number of samples, $q$ is the modulus, and $σ$ is the magnitude of the noise (defined suitably for the kind of noise involved). In particular, this implies search-to-decision reductions for LWE and LWR that run in time $\mathrm{poly}(n)$ even if the modulus $q$ is exponentially large, as long as the noise-to-modulus ratio $σ/q$ is non-negligible. Our reduction works for prime moduli $q$. If $q$ is composite, it instead produces a list that contains a small multiple of the solution. Prior to this work, known search-to-decision reductions for LWE and LWR either did not preserve the parameters of the problem (i.e., $m$, $n$, $σ$, and $q$), or had complexity that scaled polynomially with either $σ$ or the largest prime factor of $q$.

0.42

On Complexity of Gaussian Sampling

cs.CC stat.CO ·2026-10-14 ·Huanjian Zhou, Taiji Suzuki
theory similarity 0.58
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

Online Algorithms Cannot Find Isolated Perceptron Solutions

cs.CC cs.DSmath-phmath.PR ·2026-11-02 ·Shuangping Li, Gabe Schoenbach
theory similarity 0.58
Abstract · 33 pages, 5 figures

The binary perceptron problem asks for a length-$n$ sign vector in the intersection of $\lfloor αn\rfloor$-many independent random Gaussian half-spaces. A striking feature of this model is strong freezing: at every constraint density $α> 0$, all but a vanishing fraction of solutions are isolated -- $Ω(n)$-far from all others, in Hamming distance. Such solutions are believed to be algorithmically inaccessible. Nevertheless, efficient algorithms find solutions at some constraint densities $α$. One possible resolution of this apparent contradiction is that the solution space also contains rare well-connected structures, and that algorithms succeed by locating them. Gong, Huang, Li and Sellke (FOCS 2026) proved this for stable algorithms, by showing that such algorithms cannot locate isolated solutions with probability more than $\approx 0.84$. In this work, we study online algorithms, which receive the columns of the constraint matrix one by one and sign each irrevocably upon arrival. This is a widely used class of algorithms in discrepancy minimization, and it includes the algorithm of Jo and Lee (2026), which has one of the best provable guarantees for the binary perceptron. We prove that at any constraint density, any online algorithm outputs an isolated solution with probability $o(1)$. Our proof is based on the observation that the signs an online algorithm has already fixed can be completed to at most one isolated solution, so a successful algorithm must choose the unique correct sign for each of the last few columns. Using the exchangeability of these columns, we show that such an algorithm must match a suffix-parallel baseline, which signs each of them as if it were the next column to arrive. We then use an anti-concentration argument to show that such a baseline rarely produces a unique completion.

0.30

The Exact Online Threshold for the Asymmetric Binary Perceptron

cs.DS ·2026-09-02 ·Sunghyeon Jo, Taekyun Lee
highly cited similarity 0.58
Abstract · 56 pages

Let $G\in\mathbb{R}^{M\times N}$ have independent standard Gaussian entries. For a fixed margin $κ\in\mathbb{R}$, the asymmetric binary perceptron asks for $σ\in\{\pm1\}^N$ such that $Gσ/\sqrt{N}\geκ\mathbf{1}_M$. We study the online version of this problem, in which the columns of $G$ arrive sequentially and each sign must be chosen irrevocably before future columns are revealed. We determine the exact threshold $α_{\mathrm{on}}(κ)$ for every fixed $κ$: for $M/N\toα$ with $α<α_{\mathrm{on}}(κ)$, there is a deterministic online algorithm, using $O(MN)$ arithmetic operations and polynomial bit complexity, that succeeds with high probability, while for $α>α_{\mathrm{on}}(κ)$, no online algorithm succeeds with high probability. The threshold is characterized by a one-dimensional stochastic control problem for Brownian motion. The main difficulty is to upgrade a single-coordinate Brownian limit to simultaneous feasibility of all $M=Θ(N)$ constraints, which we do with half-line monotonicity and a short final correction block. At zero margin, we give a computer-assisted proof that $0.32747<α_{\mathrm{on}}(0)<0.36664$. In particular, every density below $0.32747$ is achievable online by such an algorithm, more than tripling the best density previously proved attainable by any polynomial-time algorithm, online or offline (the previous bound was $α\le0.1$, due to Li, Schramm, and Zhou). As $κ\to+\infty$, the online threshold agrees to first order with the offline storage capacity. As $κ\to-\infty$, it has the same asymptotic scale as the best known offline polynomial-time guarantee, while the storage capacity is larger by a factor of order $κ^2$.

0.57

Linear Regression with Self-Selection Bias in Polynomial Time

cs.DS math.STcs.LGstat.ML ·2026-11-12 ·Felix Zhou
similarity 0.58
Abstract

We revisit the problem of estimating $k$ linear regressors with self-selection bias in $n$ dimensions up to error $\varepsilon$ with the maximum self-selection criterion, as introduced by Cherapanamjeri, Daskalakis, Ilyas, and Zampetakis [CDIZ23, STOC]. Our main result is a $\mathrm{poly}(n,k,1/\varepsilon)$ time algorithm for the unknown-index variant of this problem, thereby improving upon the running times of the best known algorithms due to Gaitonde and Mossel [GM24] and Kalavasis, Mehrotra, and Zhou [KMZ26, COLT] with exponential dependence on $k$. Our algorithm succeeds in the presence of correlated noise between regressors, which captures the related setting of max-affine regression. Consequently, we also give the first polynomial-time algorithm for this problem, improving on the prior works of Ghosh, Pananjady, Guntuboyina, and Ramchandran [GPGR22, IEEE Transactions on Information Theory] and Gaitonde and Mossel [GM24] with exponential dependence on $k$. Prior works exhaustively search over a $k$-dimensional subspace spanned by the regressors, using conditional moments of the response to test candidates. In contrast, our algorithm is driven by an improved understanding of the moments of the covariates. We show that, restricting to observations with large response values, the degree-$(\log n)$ Hermite moment of the covariates approximately decomposes as a sum of tensor powers of the regressors. The first step of our algorithm can be viewed as a tensor decomposition algorithm for these implicitly represented high-order tensors, which outputs unit vectors parallel to the regressors. A secondary step based on a simple variant of ordinary least squares extracts estimates for the regressors given these unit vectors. We believe our analytic insight and algorithmic components may have applications to designing efficient algorithms for other latent-variable problems.

0.26

Monotone Local Search with Sample-Dependent Running Times

cs.DS cs.DM ·2026-11-01 ·Serge Gaspers
theory similarity 0.58
Abstract · Companion site (including certificates and Lean formalization): https://serggasp.github.io/sample-MLS-site/ ; archived at https://doi.org/10…

Monotone Local Search turns an algorithm that extends a given partial solution into an algorithm that finds a solution from scratch: sample a few elements, hope that they lie in an unknown solution, and complete them. Its known analyses bound every call of the extension algorithm by a worst-case time that depends only on the number of sampled elements, and Esmer et al. (SODA 2024) showed that no algorithm that uses the extension algorithm as a black box with this running time beats the original form by more than a polynomial factor. We let this running time depend on the actual sample. If the extension algorithm decides in time $O^*(2^{g(I,X,k)})$, for a polynomial-time computable $g$, whether a sample $X$ can be completed to a solution with at most $k$ elements, our main theorem gives a randomized algorithm with one-sided error in time $O^*(2^{ψn})$ whenever, for some solution $S$ of size $k$ and some $t$, the exponential moment $\sum_{X\subseteq S,|X|=t}2^{-g(I,X,k)}$ is at least $2^{-ψn}\binom{n}{t}$. A corollary, multivariate Monotone Local Search, generalizes the theorems of Fomin et al. (STOC 2016, J. ACM 2019) and of Gaspers and Lee (ICALP 2017). For Max Leaf Spanning Tree and, equivalently, Connected Dominating Set, the previous best polynomial-space bound is $O^*(1.8619^n)$. Completing a sample is a Steiner tree problem, solved in time exponential in the number of terminals, which varies strongly with the sample. We obtain a randomized polynomial-space algorithm in time $O(1.6991^n)$ and a deterministic one in time $(\sqrt5-\frac12)^n 2^{o(n)}=O(1.7361^n)$. For connectivity problems in which the extension algorithm's running time doubles with every component of the sample, an analysis through a partition function gives randomized polynomial-space algorithms in time $O^*(1.8^n)$ for Connected Feedback Vertex Set and $O(1.6444^n)$ for Connected Vertex Cover.

0.26