The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Shmuel Safra: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

  1. 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]
  2. 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]
  3. Adi Akavia, Shafi Goldwasser, Shmuel Safra
    Proving Hard-Core Predicates Using List Decoding. [Citation Graph (0, 0)][DBLP]
    FOCS, 2003, pp:146-0 [Conf]
  4. Sanjeev Arora, Shmuel Safra
    Probabilistic Checking of Proofs; A New Characterization of NP [Citation Graph (0, 0)][DBLP]
    FOCS, 1992, pp:2-13 [Conf]
  5. 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]
  6. 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]
  7. Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
    Testing Juntas. [Citation Graph (0, 0)][DBLP]
    FOCS, 2002, pp:103-112 [Conf]
  8. Shmuel Safra
    On the Complexity of omega-Automata [Citation Graph (0, 0)][DBLP]
    FOCS, 1988, pp:319-327 [Conf]
  9. Amnon Ta-Shma, David Zuckerman, Shmuel Safra
    Extractors from Reed-Muller Codes. [Citation Graph (0, 0)][DBLP]
    FOCS, 2001, pp:638-647 [Conf]
  10. Ehud Y. Shapiro, Shmuel Safra
    Fast Multiway Merge Using Destructive Operation. [Citation Graph (0, 0)][DBLP]
    ICPP, 1985, pp:118-122 [Conf]
  11. Shmuel Safra, Ehud Y. Shapiro
    Meta Interpreters For Real (Invited Paper). [Citation Graph (0, 0)][DBLP]
    IFIP Congress, 1986, pp:271-278 [Conf]
  12. 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]
  13. Johan Håstad, Steven Phillips, Shmuel Safra
    A Well-Characterized Approximation Problem. [Citation Graph (0, 0)][DBLP]
    ISTCS, 1993, pp:261-265 [Conf]
  14. Orna Kupferman, Shmuel Safra, Moshe Y. Vardi
    Relating Word and Tree Automata. [Citation Graph (0, 0)][DBLP]
    LICS, 1996, pp:322-332 [Conf]
  15. 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]
  16. 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]
  17. 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]
  18. Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra
    On the complexity of equilibria. [Citation Graph (0, 0)][DBLP]
    STOC, 2002, pp:67-71 [Conf]
  19. 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]
  20. Irit Dinur, Shmuel Safra
    The importance of being biased. [Citation Graph (0, 0)][DBLP]
    STOC, 2002, pp:33-42 [Conf]
  21. 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]
  22. 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]
  23. 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]
  24. Shmuel Safra, Moshe Y. Vardi
    On omega-Automata and Temporal Logic (Preliminary Report) [Citation Graph (0, 0)][DBLP]
    STOC, 1989, pp:127-137 [Conf]
  25. 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]
  26. Elad Hazan, Shmuel Safra, Oded Schwartz
    On the complexity of approximating k-set packing. [Citation Graph (0, 0)][DBLP]
    Computational Complexity, 2006, v:15, n:1, pp:20-39 [Journal]
  27. 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]
  28. 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]
  29. 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]
  30. 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]
  31. 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]
  32. 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]
  33. 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]
  34. 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]
  35. 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]
  36. 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]
  37. 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]
  38. 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]
  39. 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]
  40. 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]
  41. 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]
  42. 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]
  43. 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]
  44. 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]
  45. 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]
  46. 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]
  47. 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]
  48. 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]
  49. 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]
  50. 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]
  51. 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]
  52. Noga Alon, Dana Moshkovitz, Shmuel Safra
    Algorithmic construction of sets for k-restrictions. [Citation Graph (0, 0)][DBLP]
    ACM Transactions on Algorithms, 2006, v:2, n:2, pp:153-177 [Journal]

Search in 0.020secs, Finished in 0.024secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002