1 citations · 2 across the 4 of their papers we have counts for
4 papers
Parallel Repetition for the GHZ Game: Exponential Decay
Mark Braverman, Subhash Khot, Dor Minzer
We show that the value of the -fold repeated GHZ game is at most , improving upon the polynomial bound established by Holmgren and Raz. Our result is established via…
Rounding via Low Dimensional Embeddings
Mark Braverman, Dor Minzer
A regular graph is an small-set expander if for any set of vertices of fractional size at most , at least of the edges that are adjac…
Approaching the Soundness Barrier: A Near Optimal Analysis of the Cube versus Cube Test
Dor Minzer, Kai Zheng
The Cube versus Cube test is a variant of the well-known Plane versus Plane test of Raz and Safra, in which to each -dimensional affine subspace of , a polyn…
Improved Monotonicity Testers via Hypercube Embeddings
Mark Braverman, Subhash Khot, Guy Kindler +1
We show improved monotonicity testers for the Boolean hypercube under the -biased measure, as well as over the hypergrid . Our results are: 1. For any , for t…