Shmuel Safra

Publication Activity (10 Years)

Years Active: 1985-2011
Publications (10 Years): 0

Publications

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