All reports by Author Shmuel Safra:

__
TR03-020
| 27th March 2003
__

Elad Hazan, Shmuel Safra, Oded Schwartz#### On the Hardness of Approximating k-Dimensional Matching

__
TR01-104
| 17th December 2001
__

Irit Dinur, Shmuel Safra#### The Importance of Being Biased

__
TR01-036
| 2nd May 2001
__

Amnon Ta-Shma, David Zuckerman, Shmuel Safra#### Extractors from Reed-Muller Codes

__
TR98-066
| 3rd November 1998
__

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra#### PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

__
TR98-048
| 6th July 1998
__

Irit Dinur, Guy Kindler, Shmuel Safra#### Approximating CVP to Within Almost Polynomial Factor is NP-Hard

Elad Hazan, Shmuel Safra, Oded Schwartz

We study bounded degree graph problems, mainly the problem of

k-Dimensional Matching \emph{(k-DM)}, namely, the problem of

finding a maximal matching in a k-partite k-uniform balanced

hyper-graph. We prove that k-DM cannot be efficiently approximated

to within a factor of $ O(\frac{k}{ \ln k}) $ unless $P = NP$.

This ...
more >>>

Irit Dinur, Shmuel Safra

We show Minimum Vertex Cover NP-hard to approximate to within a factor

of 1.3606. This improves on the previously known factor of 7/6.

Amnon Ta-Shma, David Zuckerman, Shmuel Safra

Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the other to pseudorandom generators. A third view, regarding extractors as good error correcting codes, was noticed before. Yet, ... more >>>

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

This paper strengthens the low-error PCP characterization of NP, coming

closer to the ultimate BGLR conjecture. Namely, we prove that witnesses for

membership in any NP language can be verified with a constant

number of accesses, and with an error probability exponentially

small in the ...
more >>>

Irit Dinur, Guy Kindler, Shmuel Safra

This paper shows finding the closest vector in a lattice

to be NP-hard to approximate to within any factor up to

$2^{(\log{n})^{1-\epsilon}}$ where

$\epsilon = (\log\log{n})^{-\alpha}$

and $\alpha$ is any positive constant $<{1\over 2}$.