Online
Papers
|
|
- On Non-approximability for Quadratic
Programs
with Sanjeev Arora, Ely Berger, Elad Hazan and Guy Kindler
- Threshold Phenomena and Influence
with
some perspectives from Mathematics, Computer Science and Economics
with Gil Kalai
- Algorithmic
Construction of Sets for k-Restrictions
with Noga Alon and Dana Moshkovitz
- The
Complexity of Low-Distortion Embeddings Between Point Sets
with Christos Papadimitriou
- Proving
Hardcore Predicates Using List Decoding
with Adi Akavia and Shafi Goldwasser
- Noise-Resistant
Boolean-Functions are Juntas
with Guy Kindler
- Testing
Juntas (journal version, pdf)
with Eldar Fischer, Guy Kindler, Dana Ron and Alex Samorodnitsky
- On
the complexity of approximating TSP with neighborhoods and related problems
with Oded Schwartz
- On
the Hardness of Approximating k-Dimensional Matching
with Elad Hazan and Oded
Schwartz
- The
importance of being biased
or On the Hardness of Approximating Minimum Vertex Cover
with Irit Dinur
- On
the Complexity of Equilibria
with Xiaotie Deng and Christos
Papadimitriou
-
Extractors
from Reed-Muller Codes (PDF,
PPT)
with Amnon Ta-Shma and David Zuckerman
-
On
the hardness of approximatin label-cover
I.
Dinur, S. Safra
- Approximating-CVP
to Within Almost-Polynomial Factors is NP-hard I.
Dinur, G. Kindler,
S. Safra; Proc. of 39th FOCS (1998) A
PowerPoint presentation, by Irit
Dinur
- PCP
Characterizations of NP: Towards a Polynomially-Small Error-Probability
I. Dinur, E.
Fischer, R. Raz, G. Kindler,
S. Safra; Proc. of 31st STOC (1999) ( DVI
version )
- Approximating
shortest lattice vectors is not harder than approximating closest lattice
vectors O. Goldreich,
D. Micciancio, S.
Safra, J. Seifert
In
ECCC
- Exponential
determinization of omega-automata with strong-fairness acceptance condition
S. Safra
- Complexity
of automata on infinite objects
S. Safra, PhD thesis
|
