{"id":"arxiv/2604.23193","url":"https://arxiv.org/abs/2604.23193","tags":["cs.DS","cs.LG","math.NA","math.PR","stat.ML"],"score":0,"title":"Well-Conditioned Oblivious Perturbations in Linear Space","domain":"cs.DS","source":"arxiv","authors":["Shabarish Chenakkod","Michał Dereziński","Xiaoyu Dong","Mark Rudelson"],"reviews":0,"subject":"cs.DS","summary":"Perturbing a deterministic $n$-dimensional matrix with small Gaussian noise is a cornerstone of smoothed analysis of algorithms [Spielman and Teng, JACM 2004], as it reduces the condition number of the input to $O(n)$, and with it the complexity of many matrix algorithms. However, when deployed algorithmically, these perturbations are expensive due to the cost of generating and storing $n^2$ Gaussian random variables. We propose a perturbation that requires generating and storing $O(n)$ random numbers in $O(\\log n)$ bits of precision, and reduces the condition number of any deterministic…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-25","reactions":{}}