All reports by Author Dor Minzer:

__
TR22-167
| 23rd November 2022
__

Mark Braverman, Subhash Khot, Dor Minzer#### Parallel Repetition for the GHZ Game: Exponential Decay

__
TR22-061
| 30th April 2022
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable $k$-CSPs: I

__
TR21-091
| 29th June 2021
__

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma#### Expander Random Walks: The General Case and Limitations

__
TR20-009
| 6th February 2020
__

Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality

__
TR19-141
| 22nd October 2019
__

Mark Braverman, Subhash Khot, Dor Minzer#### On Rich $2$-to-$1$ Games

__
TR18-078
| 23rd April 2018
__

Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra#### Small Set Expansion in The Johnson Graph

__
TR18-006
| 10th January 2018
__

Subhash Khot, Dor Minzer, Muli Safra#### Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion

Revisions: 2

__
TR17-094
| 25th May 2017
__

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### On Non-Optimally Expanding Sets in Grassmann Graphs

__
TR16-198
| 14th December 2016
__

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### Towards a Proof of the 2-to-1 Games Conjecture?

__
TR15-011
| 22nd January 2015
__

Subhash Khot, Dor Minzer, Muli Safra#### On Monotonicity Testing and Boolean Isoperimetric type Theorems

Mark Braverman, Subhash Khot, Dor Minzer

We show that the value of the $n$-fold repeated GHZ game is at most $2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.

more >>>Amey Bhangale, Subhash Khot, Dor Minzer

We consider the $P$-CSP problem for $3$-ary predicates $P$ on satisfiable instances. We show that under certain conditions on $P$ and a $(1,s)$ integrality gap instance of the $P$-CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness $s+\varepsilon$, for every constant $\varepsilon>0$. ... more >>>

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma

Cohen, Peri and Ta-Shma (STOC'21) considered the following question: Assume the vertices of an expander graph are labelled by $\pm 1$. What "test" functions $f : \{\pm 1\}^t \to \{\pm1 \}$ can or cannot distinguish $t$ independent samples from those obtained by a random walk? [CPTS'21] considered only balanced labelling, ... more >>>

Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL

Theorem, Friedgutâ€™s Junta Theorem, and Talagrandâ€™s strengthening of the KKL Theorem. We follow a

new approach: looking at the first Fourier level of the function after a suitable random restriction and

applying the Log-Sobolev ...
more >>>

Mark Braverman, Subhash Khot, Dor Minzer

We propose a variant of the $2$-to-$1$ Games Conjecture that we call the Rich $2$-to-$1$ Games Conjecture and show that it is equivalent to the Unique Games Conjecture. We are motivated by two considerations. Firstly, in light of the recent proof of the $2$-to-$1$ Games Conjecture, we hope to understand ... more >>>

Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra

This paper studies expansion properties of the (generalized) Johnson Graph. For natural numbers

t < l < k, the nodes of the graph are sets of size l in a universe of size k. Two sets are connected if

their intersection is of size t. The Johnson graph arises often ...
more >>>

Subhash Khot, Dor Minzer, Muli Safra

We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes

the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a

contribution from [BKT].

The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves ... more >>>

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

The paper investigates expansion properties of the Grassmann graph,

motivated by recent results of [KMS, DKKMS] concerning hardness

of the Vertex-Cover and of the $2$-to-$1$ Games problems. Proving the

hypotheses put forward by these papers seems to first require a better

understanding of these expansion properties.

We consider the edge ... more >>>

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

We propose a combinatorial hypothesis regarding a subspace vs. subspace agreement test, and prove that if correct it leads to a proof of the 2-to-1 Games Conjecture, albeit with imperfect completeness.

Subhash Khot, Dor Minzer, Muli Safra

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we

give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function

$f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is $\epsilon$-far from

being monotone ...
more >>>