Shmuel Safra

57 papers A* 17A 1B 1Journal 32Unranked 5
YearRankTypeTitle / Venue / Authors
2011 J jnl
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability.
Comput. Complex.
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
2008 J jnl
The Erdös-Hajnal conjecture for bull-free graphs.
J. Comb. Theory B
Maria Chudnovsky, Shmuel Safra
2006 J jnl
Algorithmic construction of sets for
ACM Trans. Algorithms
Noga Alon, Dana Moshkovitz, Shmuel Safra
2006 J jnl
Exponential Determinization for omega-Automata with a Strong Fairness Acceptance Condition.
SIAM J. Comput.
Shmuel Safra
2006 J jnl
Extractors from Reed-Muller codes.
J. Comput. Syst. Sci.
Amnon Ta-Shma, David Zuckerman, Shmuel Safra
2006 J jnl
On the complexity of approximating
Comput. Complex.
Elad Hazan, Shmuel Safra, Oded Schwartz
2006 J jnl
On the complexity of approximating tsp with neighborhoods and related problems.
Comput. Complex.
Shmuel Safra, Oded Schwartz
2006 J jnl
Relating word and tree automata.
Ann. Pure Appl. Log.
Orna Kupferman, Shmuel Safra, Moshe Y. Vardi
2006 — ch.
Threshold Phenomena and Influence: Perspectives from Mathematics, Computer Science, and Economics.
Computational Complexity and Statistical Physics
Gil Kalai, Shmuel Safra
2005 A* conf
The complexity of low-distortion embeddings between point sets.
SODA
Christos H. Papadimitriou, Shmuel Safra
2004 J jnl
On the hardness of approximating label-cover.
Inf. Process. Lett.
Irit Dinur, Shmuel Safra
2004 J jnl
Testing juntas.
J. Comput. Syst. Sci.
Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
2003 J jnl
Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.
Comb.
Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra
2003 A conf
On the Complexity of Approximating TSP with Neighborhoods and Related Problems.
ESA
Shmuel Safra, Oded Schwartz
2003 — conf
On the Complexity of Approximating k-Dimensional Matching.
RANDOM-APPROX
Elad Hazan, Shmuel Safra, Oded Schwartz
2003 J jnl
On the Hardness of Approximating k-Dimensional Matching
Electron. Colloquium Comput. Complex.
Elad Hazan, Shmuel Safra, Oded Schwartz
2003 J jnl
On the complexity of price equilibria.
J. Comput. Syst. Sci.
Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra
2003 A* conf
Proving Hard-Core Predicates Using List Decoding.
FOCS
Adi Akavia, Shafi Goldwasser, Shmuel Safra
2002 A* conf
On the complexity of equilibria.
STOC
Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra
2002 A* conf
Testing Juntas.
FOCS
Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
2002 A* conf
The importance of being biased.
STOC
Irit Dinur, Shmuel Safra
2001 J jnl
Extractors from Reed-Muller Codes
Electron. Colloquium Comput. Complex.
Amnon Ta-Shma, David Zuckerman, Shmuel Safra
2001 A* conf
Extractors from Reed-Muller Codes.
FOCS
Amnon Ta-Shma, David Zuckerman, Shmuel Safra
2001 J jnl
The Importance of Being Biased
Electron. Colloquium Comput. Complex.
Irit Dinur, Shmuel Safra
2000 J jnl
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.
SIAM J. Comput.
Oded Goldreich, Shmuel Safra
2000 J jnl
On the Hardness of Approximating the Chromatic Number.
Comb.
Sanjeev Khanna, Nathan Linial, Shmuel Safra
1999 J jnl
Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert
1999 J jnl
Approximating Shortest Lattice Vectors is not Harder than Approximating Closest Lattice Vectors.
Inf. Process. Lett.
Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert
1999 J jnl
On the Hardness of Approximating Label Cover
Electron. Colloquium Comput. Complex.
Irit Dinur, Shmuel Safra
1999 A* conf
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.
STOC
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
1998 J jnl
Approximating CVP to Within Almost Polynomial Factor is NP-Hard
Electron. Colloquium Comput. Complex.
Irit Dinur, Guy Kindler, Shmuel Safra
1998 A* conf
Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard.
FOCS
Irit Dinur, Guy Kindler, Shmuel Safra
1998 J jnl
On Data Structures and Asymmetric Communication Complexity.
J. Comput. Syst. Sci.
Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson
1998 J jnl
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability
Electron. Colloquium Comput. Complex.
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
1998 J jnl
Probabilistic Checking of Proofs: A New Characterization of NP.
J. ACM
Sanjeev Arora, Shmuel Safra
1997 — conf
A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.
RANDOM
Oded Goldreich, Shmuel Safra
1997 A* conf
A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP.
STOC
Ran Raz, Shmuel Safra
1996 J jnl
A Combinatorial Consistency Lemma with application to the PCP Theorem
Electron. Colloquium Comput. Complex.
Oded Goldreich, Shmuel Safra
1996 J jnl
Interactive Proofs and the Hardness of Approximating Cliques.
J. ACM
Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy
1996 A* conf
Relating Word and Tree Automata.
LICS
Orna Kupferman, Shmuel Safra, Moshe Y. Vardi
1995 A* conf
On data structures and asymmetric communication complexity.
STOC
Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson
1994 J jnl
On Planning while Learning.
CoRR
Shmuel Safra, Moshe Tennenholtz
1994 J jnl
On Planning while Learning.
J. Artif. Intell. Res.
Shmuel Safra, Moshe Tennenholtz
1993 — conf
A Well-Characterized Approximation Problem.
ISTCS
Johan Håstad, Steven J. Phillips, Shmuel Safra
1993 J jnl
A Well-Characterized Approximation Problem.
Inf. Process. Lett.
Johan Håstad, Steven J. Phillips, Shmuel Safra
1993 — conf
On the Hardness of Approximating the Chromatic Number.
ISTCS
Sanjeev Khanna, Nathan Linial, Shmuel Safra
1992 A* conf
Exponential Determinization for omega-Automata with Strong-Fairness Acceptance Condition (Extended Abstract)
STOC
Shmuel Safra
1992 A* conf
Low Communication 2-Prover Zero-Knowledge Proofs for NP.
CRYPTO
Cynthia Dwork, Uriel Feige, Joe Kilian, Moni Naor, Shmuel Safra
1992 A* conf
Probabilistic Checking of Proofs; A New Characterization of NP
FOCS
Sanjeev Arora, Shmuel Safra
1991 A* conf
Approximating Clique is Almost NP-Complete (Preliminary Version)
FOCS
Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy
1989 A* conf
On omega-Automata and Temporal Logic (Preliminary Report)
STOC
Shmuel Safra, Moshe Y. Vardi
1988 A* conf
On the Complexity of omega-Automata
FOCS
Shmuel Safra
1987 J jnl
Notes on the Complexity of Systolic Programs.
J. Parallel Distributed Comput.
Stephen Taylor, Lisa Hellerstein, Shmuel Safra, Ehud Shapiro
1986 J jnl
A parallel implementation of Flat Concurrent Prolog.
Int. J. Parallel Program.
Stephen Taylor, Shmuel Safra, Ehud Shapiro
1986 — conf
Meta Interpreters For Real (Invited Paper).
IFIP Congress
Shmuel Safra, Ehud Shapiro
1986 J jnl
Multiway Merge with Constant Delay in Concurrent Prolog.
New Gener. Comput.
Ehud Shapiro, Shmuel Safra
1985 B conf
Fast Multiway Merge Using Destructive Operation.
ICPP
Ehud Shapiro, Shmuel Safra