603 citations · 1.6k across the 72 of their papers we have counts for
6 papers · 1 filter
Efficient Rounding for the Noncommutative Grothendieck Inequality
Assaf Naor, Oded Regev, Thomas Vidick
The classical Grothendieck inequality has applications to the design of approximation algorithms for $\cclass{NP}$-hard optimization problem…
Locally decodable codes and the failure of cotype for projective tensor products
Jop Briet, Assaf Naor, Oded Regev
It is shown that for every there exists a Banach space of finite cotype such that the projective tensor product $\ell_p\tp X$ fails to have finite cotype. Mor…
Quantum XOR Games
Oded Regev, Thomas Vidick
We introduce quantum XOR games, a model of two-player one-round games that extends the model of XOR games by allowing the referee's questions to the players to be quantum states. W…
Elementary Proofs of Grothendieck Theorems for Completely Bounded Norms
Oded Regev, Thomas Vidick
We provide alternative proofs of two recent Grothendieck theorems for jointly completely bounded bilinear forms, originally due to Pisier and Shlyakhtenko (Invent. Math. 2002) and…
Krivine schemes are optimal
Assaf Naor, Oded Regev
It is shown that for every there exists a Borel probability measure on such that for every and $x_1,..., x_m,y…
Impossibility of a Quantum Speed-up with a Faulty Oracle
Oded Regev, Liron Schiff
We consider Grover's unstructured search problem in the setting where each oracle call has some small probability of failing. We show that no quantum speed-up is possible in this c…