All reports by Author Muli Safra:

__
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

__
TR12-109
| 31st August 2012
__

Subhash Khot, Muli Safra, Madhur Tulsiani#### Towards An Optimal Query Efficient PCP?

__
TR07-102
| 4th October 2007
__

Andrej Bogdanov, Muli Safra#### Hardness amplification for errorless heuristics

__
TR05-058
| 24th May 2005
__

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra#### On Non-Approximability for Quadratic Programs

__
TR96-047
| 2nd September 1996
__

Oded Goldreich, Muli Safra#### A Combinatorial Consistency Lemma with application to the PCP Theorem

Revisions: 1

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

Subhash Khot, Muli Safra, Madhur Tulsiani

We construct a PCP based on the hyper-graph linearity test with 3 free queries. It has near-perfect completeness and soundness strictly less than 1/8. Such a PCP was known before only assuming the Unique Games Conjecture, albeit with soundness arbitrarily close to 1/16.

At a technical level, our ...
more >>>

Andrej Bogdanov, Muli Safra

An errorless heuristic is an algorithm that on all inputs returns either the correct answer or the special symbol "I don't know." A central question in average-case complexity is whether every distributional decision problem in NP has an errorless heuristic scheme: This is an algorithm that, for every δ > ... more >>>

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra

This paper studies the computational complexity of the following type of

quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find $x \in \{-1,+1\}^n$ that maximizes $x^TA x$. This problem recently attracted attention due to its application in various clustering settings (Charikar and Wirth, 2004) as well as ...
more >>>

Oded Goldreich, Muli Safra

The current proof of the PCP Theorem (i.e., NP=PCP(log,O(1)))

is very complicated.

One source of difficulty is the technically involved

analysis of low-degree tests.

Here, we refer to the difficulty of obtaining strong results

regarding low-degree tests; namely, results of the type obtained and

used by ...
more >>>