Well-Conditioned Oblivious Perturbations in Linear Space
arXiv:2604.23193v1 Announce Type: cross
Abstract: 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…