Showing 2025Show all
2 papers · 1 filter
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…