Amulya Musipatla

dblp:278/1693 · DBLP profile ↗
← Back
2ranked-venue papers
1as first author
2since 2021 · last 2022
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 1 first-author · 2 since 2021
YearPublicationVenuePosition
2022 The SDP Value of Random 2CSPs
abstract
We consider a very wide class of models for sparse random Boolean 2CSPs; equivalently, degree-2 optimization problems over~$\{\pm 1\}^n$. For each model $\mathcal{M}$, we identify the "high-probability value"~$s^*_{\mathcal{M}}$ of the natural SDP relaxation (equivalently, the quantum value). That is, for all $\varepsilon > 0$ we show that the SDP optimum of a random $n$-variable instance is (when normalized by~$n$) in the range $(s^*_{\mathcal{M}}-\varepsilon, s^*_{\mathcal{M}}+\varepsilon)$ with high probability. Our class of models includes non-regular CSPs, and ones where the SDP relaxation value is strictly smaller than the spectral relaxation value.
Amulya Musipatla, Ryan O'Donnell, Tselil Schramm
ICALP1
2022 Noisy Boolean Hidden Matching with Applications
Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou
ITCS2