dblp.uni-trier.dewww.uni-trier.de

Shmuel Safra Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

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

Coauthor Index

1Adi Akavia [42]
2Noga Alon [52]
3Sanjeev Arora [9] [22]
4Maria Chudnovsky [53]
5Xiaotie Deng [35] [38]
6Irit Dinur [23] [24] [25] [28] [29] [33] [36] [40] [45]
7Cynthia Dwork [10]
8Uriel Feige [7] [10] [16]
9Eldar Fischer [23] [29] [37] [44]
10Oded Goldreich [17] [20] [26] [27] [30]
11Shafi Goldwasser [7] [16] [42]
12Johan Håstad [11] [12]
13Elad Hazan [39] [41] [49]
14Lisa Hellerstein [4]
15Sanjeev Khanna [13] [31]
16Joe Kilian [10]
17Guy Kindler [23] [24] [25] [29] [37] [40] [44]
18Orna Kupferman [18] [51]
19Nathan Linial (Nati Linial) [13] [31]
20László Lovász [7] [16]
21Daniele Micciancio [26] [27]
22Peter Bro Miltersen [15] [21]
23Dana Moshkovitz [52]
24Moni Naor [10]
25Noam Nisan [15] [21]
26Christos H. Papadimitriou [35] [38] [46]
27Steven Phillips [11] [12]
28Ran Raz [19] [23] [29] [40]
29Dana Ron [37] [44]
30Alex Samorodnitsky [37] [44]
31Oded Schwartz [39] [41] [43] [49] [50]
32Jean-Pierre Seifert [26] [27]
33Ehud Y. Shapiro [1] [2] [3] [4]
34Mario Szegedy [7] [16]
35Amnon Ta-Shma [32] [34] [48]
36Stephen Taylor [4]
37Moshe Tennenholtz [14]
38Moshe Y. Vardi [6] [18] [51]
39Avi Wigderson [15] [21]
40David Zuckerman [32] [34] [48]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)