20 citations · 29 across the 8 of their papers we have counts for
15 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…
On the Largest Product-free Subsets of the Alternating Groups
Peter Keevash, Noam Lifshitz, Dor Minzer
A subset of a group is called product-free if there is no solution to with all in . It is easy to see that the largest product-free subset of the symmetri…
Improved Optimal Testing Results from Global Hypercontractivity
Tali Kaufman, Dor Minzer
The problem of testing low-degree polynomials has received significant attention over the years due to its importance in theoretical computer science, and in particular in complexi…