Fetching the paper…
Reading the bibliography…
For every $\epsilon>0$, we give an $\exp(\tilde{O}(\sqrt{n}/\epsilon^2))$-time algorithm for the $1$ vs $1-\epsilon$ \emph{Best Separable State (BSS)} problem of distinguishing, given an $n^2\times n^2$ matrix $\mathcal{M}$ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state $\rho$ that $\mathcal{M}$ accepts with probability $1$, and the case that every separable state is accepted with probability at most $1-\epsilon$.
A. J. Stam, Limit theorems for uniform distributions on spheres in high-dimensional Euclidean spaces , J. Appl. Probab. 19
1982
Earlier work this paper cites.
László Lovász and Michael E. Saks, Lattices, möbius functions and communication complexity , FOCS, IEEE Computer Society, 1988, pp. 81–90
1988
Earlier work this paper cites.
Noam Nisan and Avi Wigderson, On rank vs. communication complexity , FOCS, IEEE Computer Society, 1994, pp. 831–836
1994
Earlier work this paper cites.
Michał Horodecki, Paweł Horodecki, and Ryszard Horodecki, Separability of mixed states: necessary and sufficient conditions , Physics Letters A 223
1996
Earlier work this paper cites.
Maciej Lewenstein, B Kraus, JI Cirac, and P Horodecki, Optimization of entanglement witnesses , Physical Review A 62
2000
Earlier work this paper cites.
Pablo A Parrilo, Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization , Ph.D. thesis, Citeseer, 2000
2000
Earlier work this paper cites.
Bruce Reznick, Some concrete aspects of hilbert’s 17th problem , Contemporary Mathematics 253
2000
Earlier work this paper cites.
Jean B. Lasserre, An explicit exact SDP relaxation for nonlinear 0-1 programs , IPCO, Lecture Notes in Computer Science, vol. 2081, Springer, 2001, pp. 293–303
2001
Earlier work this paper cites.
Leonid Gurvits, Classical deterministic complexity of edmonds’ problem and quantum entanglement , Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, ACM, 2003, pp. 10–19
2003
Earlier work this paper cites.
Guifré Vidal, Efficient classical simulation of slightly entangled quantum computations , Phys. Rev. Lett. 91
2003
Cited alongside, same era.
Andrew C Doherty, Pablo A Parrilo, and Federico M Spedalieri, Complete family of separability criteria , Physical Review A 69
2004
Cited alongside, same era.
Vlatko Vedral, Quantifying entanglement in macroscopic systems , Nature 453
2008
Cited alongside, same era.
Hugue Blier and Alain Tapp, All languages in np have very short quantum proofs , Quantum, Nano and Micro Technologies, 2009. ICQNM’09. Third International Conference on, IEEE, 2009, pp. 34–37
2009
Cited alongside, same era.
Sevag Gharibian, Strong np-hardness of the quantum separability problem , Quantum Information & Computation 10
2010
Cited alongside, same era.
Scott Aaronson, Russell Impagliazzo, and Dana Moshkovitz, AM with multiple merlins , Electronic Colloquium on Computational Complexity (ECCC) 21
2014
Later among the works it cites.
Dmitry Gavinsky and Shachar Lovett, En route to the log-rank conjecture: New reductions and equivalent formulations , ICALP (1), Lecture Notes in Computer Science, vol. 8572, Springer, 2014, pp. 514–524
2014
Later among the works it cites.
Shachar Lovett, Communication is bounded by root of rank , STOC, ACM, 2014, pp. 842–846
2014
Later among the works it cites.
2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Fernando G.S.L. Brandão, Matthias Christandl, and Jon Yard, A quasipolynomial-time algorithm for the quantum separability problem , Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’11, ACM, 2011, pp. 343–352
2011
Cited alongside, same era.
Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou, Hypercontractivity, sum-of-squares proofs, and their applications , STOC, ACM, 2012, pp. 307–326
2012
Cited alongside, same era.
2012
Cited alongside, same era.
Aram Wettroth Harrow and Ashley Montanaro, Testing product states, quantum merlin-arthur games and tensor optimization , J. ACM 60
2013
Cited alongside, same era.
2015
Later among the works it cites.
Boaz Barak, Jonathan A. Kelner, and David Steurer, Dictionary learning and tensor decomposition via the sum-of-squares method , STOC, ACM, 2015, pp. 143–151
2015
Later among the works it cites.
Jean Bernard Lasserre, An introduction to polynomial and semi-algebraic optimization , no. 52, Cambridge University Press, 2015
2015
Later among the works it cites.
2016
Later among the works it cites.
Boaz Barak, Pravesh Kothari, and David Steurer, Proofs, beliefs, and algorithms through the lens of sum-of-squares , 2016, Lecture notes in preparation, available on http://sumofsquares.org
2016
Later among the works it cites.