12 citations · 51 across the 12 of their papers we have counts for
15 papers
Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality
Yeongwoo Hwang, Joe Neeman, Ojas Parekh +2
The Gaussian noise stability of a function is the expected value of over -correlated Gaussian random v…
Quantum soundness of the classical low individual degree test
Zhengfeng Ji, Anand Natarajan, Thomas Vidick +2
Low degree tests play an important role in classical complexity theory, serving as basic ingredients in foundational results such as [BFL91] and the…
NEEXP in MIP*
Anand Natarajan, John Wright
We study multiprover interactive proof systems. The power of classical multiprover interactive proof systems, in which the provers do not share entanglement, was characterized in a…
Quantum state certification
Costin Bădescu, Ryan O'Donnell, John Wright
We consider the problem of quantum state certification, where one is given copies of an unknown -dimensional quantum mixed state , and one wants to test whether is eq…
Which Distribution Distances are Sublinearly Testable?
Constantinos Daskalakis, Gautam Kamath, John Wright
Given samples from an unknown distribution and a description of a distribution , are and close or far? This question of "identity testing" has received significant a…
Efficient quantum tomography II
Ryan O'Donnell, John Wright
Following [OW16], we continue our analysis of: (1) "Quantum tomography", i.e., learning a quantum state, i.e., the quantum generalization of learning a discrete probability distrib…