Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Dor Minzer:

TR17-094 | 25th May 2017
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

On Non-Optimally Expanding Sets in Grassmann Graphs

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 >>>

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?

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.

more >>>

TR15-011 | 22nd January 2015
Subhash Khot, Dor Minzer, Muli Safra

On Monotonicity Testing and Boolean Isoperimetric type Theorems

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 >>>

ISSN 1433-8092 | Imprint