5 papers
A Simple Algorithm for Best Separable State
Prashanti Anderson, Samuel B. Hopkins, Amit Rajaraman
We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states. In classical terms, the goal is…
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…
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…
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…
Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins +2
Metric embeddings are a widely used method in algorithm design, where generally a ``complex'' metric is embedded into a simpler, lower-dimensional one. Historically, the theoretica…