M. Rudelson

collaborators

3 papers

math.PR2026

Well-invertible column subsets of sparse matrices are rare

Han Huang, Mark Rudelson, Konstantin Tikhomirov

A random $n \times k$ matrix $S$ is an \emph{ $(r, I^\pm)$ -oblivious subspace injection} (OSI) if $E ∥ S^{⊤} x ∥_{2}^{2} = ∥ x ∥_{2}^{2}$ for every $x \in R^{n}$ , and for every fixed…

cs.DS2026

Well-Conditioned Oblivious Perturbations in Linear Space

Shabarish Chenakkod, MichaÅ DereziÅski, Xiaoyu Dong +1

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 co…

math.FA2026

Hardness of approximation of centered convex bodies by polytopes

Han Huang, Mark Rudelson

The distance between convex bodies $K, L \subseteq \R^n$ is defined as \[ d(K,L)= \inf \left\{ Î»\ge 1: \ L-x \subseteq T (K-y) \subseteq Î»(L-x) \right\}, \] where the infimum i…