3 papers
cs.DS2026
Entrywise Low-Rank Approximation and Matrix Norms via Global Correlation Rounding
Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins
Given a matrix , the goal of the entrywise low-rank approximation problem is to find over all rank- matrices , where is t…
cs.DS2025
Faster MAX-CUT on Bounded Threshold Rank Graphs
Prashanti Anderson, Samuel B. Hopkins, Amit Rajaraman +1
We design new algorithms for approximating 2CSPs on graphs with bounded threshold rank, that is, whose normalized adjacency matrix has few eigenvalues larger than , sm…
cs.DS2025
Additive Approximation Schemes for Low-Dimensional Embeddings
Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins
We consider the task of fitting low-dimensional embeddings to high-dimensional data. In particular, we study the -Euclidean Metric Violation problem ($\textsf{$k$-EMV}$), where…