The SCEAS System
| |||||||

## Search the dblp DataBase
Shmuel Safra:
[Publications]
[Author Rank by year]
[Co-authors]
[Prefers]
[Cites]
[Cited by]
## Publications of Author- Cynthia Dwork, Uriel Feige, Joe Kilian, Moni Naor, Shmuel Safra
**Low Communication 2-Prover Zero-Knowledge Proofs for NP.**[Citation Graph (0, 0)][DBLP] CRYPTO, 1992, pp:215-227 [Conf] - Shmuel Safra, Oded Schwartz
**On the Complexity of Approximating TSP with Neighborhoods and Related Problems.**[Citation Graph (0, 0)][DBLP] ESA, 2003, pp:446-458 [Conf] - Adi Akavia, Shafi Goldwasser, Shmuel Safra
**Proving Hard-Core Predicates Using List Decoding.**[Citation Graph (0, 0)][DBLP] FOCS, 2003, pp:146-0 [Conf] - Sanjeev Arora, Shmuel Safra
**Probabilistic Checking of Proofs; A New Characterization of NP**[Citation Graph (0, 0)][DBLP] FOCS, 1992, pp:2-13 [Conf] - Irit Dinur, Guy Kindler, Shmuel Safra
**Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard.**[Citation Graph (0, 0)][DBLP] FOCS, 1998, pp:99-111 [Conf] - Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy
**Approximating Clique is Almost NP-Complete (Preliminary Version)**[Citation Graph (0, 0)][DBLP] FOCS, 1991, pp:2-12 [Conf] - Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
**Testing Juntas.**[Citation Graph (0, 0)][DBLP] FOCS, 2002, pp:103-112 [Conf] - Shmuel Safra
**On the Complexity of omega-Automata**[Citation Graph (0, 0)][DBLP] FOCS, 1988, pp:319-327 [Conf] - Amnon Ta-Shma, David Zuckerman, Shmuel Safra
**Extractors from Reed-Muller Codes.**[Citation Graph (0, 0)][DBLP] FOCS, 2001, pp:638-647 [Conf] - Ehud Y. Shapiro, Shmuel Safra
**Fast Multiway Merge Using Destructive Operation.**[Citation Graph (0, 0)][DBLP] ICPP, 1985, pp:118-122 [Conf] - Shmuel Safra, Ehud Y. Shapiro
**Meta Interpreters For Real (Invited Paper).**[Citation Graph (0, 0)][DBLP] IFIP Congress, 1986, pp:271-278 [Conf] - Sanjeev Khanna, Nathan Linial, Shmuel Safra
**On the Hardness of Approximating the Chromatic Number.**[Citation Graph (0, 0)][DBLP] ISTCS, 1993, pp:250-260 [Conf] - Johan Håstad, Steven Phillips, Shmuel Safra
**A Well-Characterized Approximation Problem.**[Citation Graph (0, 0)][DBLP] ISTCS, 1993, pp:261-265 [Conf] - Orna Kupferman, Shmuel Safra, Moshe Y. Vardi
**Relating Word and Tree Automata.**[Citation Graph (0, 0)][DBLP] LICS, 1996, pp:322-332 [Conf] - Oded Goldreich, Shmuel Safra
**A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.**[Citation Graph (0, 0)][DBLP] RANDOM, 1997, pp:67-84 [Conf] - Elad Hazan, Shmuel Safra, Oded Schwartz
**On the Complexity of Approximating k-Dimensional Matching.**[Citation Graph (0, 0)][DBLP] RANDOM-APPROX, 2003, pp:83-97 [Conf] - Christos H. Papadimitriou, Shmuel Safra
**The complexity of low-distortion embeddings between point sets.**[Citation Graph (0, 0)][DBLP] SODA, 2005, pp:112-118 [Conf] - Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra
**On the complexity of equilibria.**[Citation Graph (0, 0)][DBLP] STOC, 2002, pp:67-71 [Conf] - Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
**PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.**[Citation Graph (0, 0)][DBLP] STOC, 1999, pp:29-40 [Conf] - Irit Dinur, Shmuel Safra
**The importance of being biased.**[Citation Graph (0, 0)][DBLP] STOC, 2002, pp:33-42 [Conf] - Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson
**On data structures and asymmetric communication complexity.**[Citation Graph (0, 0)][DBLP] STOC, 1995, pp:103-111 [Conf] - Ran Raz, Shmuel Safra
**A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP.**[Citation Graph (0, 0)][DBLP] STOC, 1997, pp:475-484 [Conf] - Shmuel Safra
**Exponential Determinization for omega-Automata with Strong-Fairness Acceptance Condition (Extended Abstract)**[Citation Graph (0, 0)][DBLP] STOC, 1992, pp:275-282 [Conf] - Shmuel Safra, Moshe Y. Vardi
**On omega-Automata and Temporal Logic (Preliminary Report)**[Citation Graph (0, 0)][DBLP] STOC, 1989, pp:127-137 [Conf] - Orna Kupferman, Shmuel Safra, Moshe Y. Vardi
**Relating word and tree automata.**[Citation Graph (0, 0)][DBLP] Ann. Pure Appl. Logic, 2006, v:138, n:1-3, pp:126-146 [Journal] - Elad Hazan, Shmuel Safra, Oded Schwartz
**On the complexity of approximating**[Citation Graph (0, 0)][DBLP]*k*-set packing. Computational Complexity, 2006, v:15, n:1, pp:20-39 [Journal] - Shmuel Safra, Oded Schwartz
**On the complexity of approximating tsp with neighborhoods and related problems.**[Citation Graph (0, 0)][DBLP] Computational Complexity, 2006, v:14, n:4, pp:281-307 [Journal] - Irit Dinur, Guy Kindler, Ran Raz, Shmuel Safra
**Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.**[Citation Graph (0, 0)][DBLP] Combinatorica, 2003, v:23, n:2, pp:205-243 [Journal] - Sanjeev Khanna, Nathan Linial, Shmuel Safra
**On the Hardness of Approximating the Chromatic Number.**[Citation Graph (0, 0)][DBLP] Combinatorica, 2000, v:20, n:3, pp:393-415 [Journal] - Amnon Ta-Shma, David Zuckerman, Shmuel Safra
**Extractors from Reed-Muller Codes**[Citation Graph (0, 0)][DBLP] Electronic Colloquium on Computational Complexity (ECCC), 2001, v:8, n:36, pp:- [Journal] - Irit Dinur, Shmuel Safra
**The Importance of Being Biased**[Citation Graph (0, 0)][DBLP] Electronic Colloquium on Computational Complexity (ECCC), 2001, v:, n:104, pp:- [Journal] - Elad Hazan, Shmuel Safra, Oded Schwartz
**On the Hardness of Approximating k-Dimensional Matching**[Citation Graph (0, 0)][DBLP] Electronic Colloquium on Computational Complexity (ECCC), 2003, v:10, n:020, pp:- [Journal] - Oded Goldreich, Shmuel Safra
**A Combinatorial Consistency Lemma with application to the PCP Theorem**[Citation Graph (0, 0)][DBLP] Electronic Colloquium on Computational Complexity (ECCC), 1996, v:3, n:47, pp:- [Journal] - Irit Dinur, Guy Kindler, Shmuel Safra
**Approximating CVP to Within Almost Polynomial Factor is NP-Hard**[Citation Graph (0, 0)][DBLP] Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:48, pp:- [Journal] - Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra
**PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability**[Citation Graph (0, 0)][DBLP] Electronic Colloquium on Computational Complexity (ECCC), 1998, v:5, n:66, pp:- [Journal] - Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert
**Approximating Shortest Lattice Vectors is Not Harder Than Approximating Closest Lattice Vectors.**[Citation Graph (0, 0)][DBLP] Electronic Colloquium on Computational Complexity (ECCC), 1999, v:6, n:2, pp:- [Journal] - Irit Dinur, Shmuel Safra
**On the Hardness of Approximating Label Cover**[Citation Graph (0, 0)][DBLP] Electronic Colloquium on Computational Complexity (ECCC), 1999, v:6, n:15, pp:- [Journal] - Irit Dinur, Shmuel Safra
**On the hardness of approximating label-cover.**[Citation Graph (0, 0)][DBLP] Inf. Process. Lett., 2004, v:89, n:5, pp:247-254 [Journal] - Oded Goldreich, Daniele Micciancio, Shmuel Safra, Jean-Pierre Seifert
**Approximating Shortest Lattice Vectors is not Harder than Approximating Closest Lattice Vectors.**[Citation Graph (0, 0)][DBLP] Inf. Process. Lett., 1999, v:71, n:2, pp:55-61 [Journal] - Johan Håstad, Steven Phillips, Shmuel Safra
**A Well-Characterized Approximation Problem.**[Citation Graph (0, 0)][DBLP] Inf. Process. Lett., 1993, v:47, n:6, pp:301-305 [Journal] - Sanjeev Arora, Shmuel Safra
**Probabilistic Checking of Proofs: A New Characterization of NP.**[Citation Graph (0, 0)][DBLP] J. ACM, 1998, v:45, n:1, pp:70-122 [Journal] - Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy
**Interactive Proofs and the Hardness of Approximating Cliques.**[Citation Graph (0, 0)][DBLP] J. ACM, 1996, v:43, n:2, pp:268-292 [Journal] - Shmuel Safra, Moshe Tennenholtz
**On Planning while Learning.**[Citation Graph (0, 0)][DBLP] J. Artif. Intell. Res. (JAIR), 1994, v:2, n:, pp:111-129 [Journal] - Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra
**On the complexity of price equilibria.**[Citation Graph (0, 0)][DBLP] J. Comput. Syst. Sci., 2003, v:67, n:2, pp:311-324 [Journal] - Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
**Testing juntas.**[Citation Graph (0, 0)][DBLP] J. Comput. Syst. Sci., 2004, v:68, n:4, pp:753-787 [Journal] - Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson
**On Data Structures and Asymmetric Communication Complexity.**[Citation Graph (0, 0)][DBLP] J. Comput. Syst. Sci., 1998, v:57, n:1, pp:37-49 [Journal] - Amnon Ta-Shma, David Zuckerman, Shmuel Safra
**Extractors from Reed-Muller codes.**[Citation Graph (0, 0)][DBLP] J. Comput. Syst. Sci., 2006, v:72, n:5, pp:786-812 [Journal] - Stephen Taylor, Lisa Hellerstein, Shmuel Safra, Ehud Y. Shapiro
**Notes on the Complexity of Systolic Programs.**[Citation Graph (0, 0)][DBLP] J. Parallel Distrib. Comput., 1987, v:4, n:3, pp:250-265 [Journal] - Ehud Y. Shapiro, Shmuel Safra
**Multiway Merge with Constant Delay in Concurrent Prolog.**[Citation Graph (0, 0)][DBLP] New Generation Comput., 1986, v:4, n:2, pp:211-216 [Journal] - Oded Goldreich, Shmuel Safra
**A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem.**[Citation Graph (0, 0)][DBLP] SIAM J. Comput., 2000, v:29, n:4, pp:1132-1154 [Journal] - Shmuel Safra
**Exponential Determinization for omega-Automata with a Strong Fairness Acceptance Condition.**[Citation Graph (0, 0)][DBLP] SIAM J. Comput., 2006, v:36, n:3, pp:803-814 [Journal] - Noga Alon, Dana Moshkovitz, Shmuel Safra
**Algorithmic construction of sets for**[Citation Graph (0, 0)][DBLP]*k*-restrictions. ACM Transactions on Algorithms, 2006, v:2, n:2, pp:153-177 [Journal]
Search in 0.008secs, Finished in 0.011secs | |||||||

| |||||||

| |||||||

System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002 for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002 |