 | 2008 |
|---|
| 53 |       | Maria Chudnovsky,
Shmuel Safra:
The Erdös-Hajnal conjecture for bull-free graphs.
J. Comb. Theory, Ser. B 98(6): 1301-1310 (2008) |
| 2006 |
|---|
| 52 | | Noga Alon,
Dana Moshkovitz,
Shmuel Safra:
Algorithmic construction of sets for k-restrictions.
ACM Transactions on Algorithms 2(2): 153-177 (2006) |
| 51 | | Orna Kupferman,
Shmuel Safra,
Moshe Y. Vardi:
Relating word and tree automata.
Ann. Pure Appl. Logic 138(1-3): 126-146 (2006) |
| 50 | | Shmuel Safra,
Oded Schwartz:
On the complexity of approximating tsp with neighborhoods and related problems.
Computational Complexity 14(4): 281-307 (2006) |
| 49 | | Elad Hazan,
Shmuel Safra,
Oded Schwartz:
On the complexity of approximating k-set packing.
Computational Complexity 15(1): 20-39 (2006) |
| 48 | | Amnon Ta-Shma,
David Zuckerman,
Shmuel Safra:
Extractors from Reed-Muller codes.
J. Comput. Syst. Sci. 72(5): 786-812 (2006) |
| 47 | | Shmuel Safra:
Exponential Determinization for omega-Automata with a Strong Fairness Acceptance Condition.
SIAM J. Comput. 36(3): 803-814 (2006) |
| 2005 |
|---|
| 46 | | Christos H. Papadimitriou,
Shmuel Safra:
The complexity of low-distortion embeddings between point sets.
SODA 2005: 112-118 |
| 2004 |
|---|
| 45 | | Irit Dinur,
Shmuel Safra:
On the hardness of approximating label-cover.
Inf. Process. Lett. 89(5): 247-254 (2004) |
| 44 | | Eldar Fischer,
Guy Kindler,
Dana Ron,
Shmuel Safra,
Alex Samorodnitsky:
Testing juntas.
J. Comput. Syst. Sci. 68(4): 753-787 (2004) |
| 2003 |
|---|
| 43 | | Shmuel Safra,
Oded Schwartz:
On the Complexity of Approximating TSP with Neighborhoods and Related Problems.
ESA 2003: 446-458 |
| 42 | | Adi Akavia,
Shafi Goldwasser,
Shmuel Safra:
Proving Hard-Core Predicates Using List Decoding.
FOCS 2003: 146- |
| 41 | | Elad Hazan,
Shmuel Safra,
Oded Schwartz:
On the Complexity of Approximating k-Dimensional Matching.
RANDOM-APPROX 2003: 83-97 |
| 40 | | Irit Dinur,
Guy Kindler,
Ran Raz,
Shmuel Safra:
Approximating CVP to Within Almost-Polynomial Factors is NP-Hard.
Combinatorica 23(2): 205-243 (2003) |
| 39 | | Elad Hazan,
Shmuel Safra,
Oded Schwartz:
On the Hardness of Approximating k-Dimensional Matching
Electronic Colloquium on Computational Complexity (ECCC) 10(020): (2003) |
| 38 | | Xiaotie Deng,
Christos H. Papadimitriou,
Shmuel Safra:
On the complexity of price equilibria.
J. Comput. Syst. Sci. 67(2): 311-324 (2003) |
| 2002 |
|---|
| 37 | | Eldar Fischer,
Guy Kindler,
Dana Ron,
Shmuel Safra,
Alex Samorodnitsky:
Testing Juntas.
FOCS 2002: 103-112 |
| 36 | | Irit Dinur,
Shmuel Safra:
The importance of being biased.
STOC 2002: 33-42 |
| 35 | | Xiaotie 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 |
| 33 | | Irit Dinur,
Shmuel Safra:
The Importance of Being Biased
Electronic Colloquium on Computational Complexity (ECCC)(104): (2001) |
| 32 | | Amnon Ta-Shma,
David Zuckerman,
Shmuel Safra:
Extractors from Reed-Muller Codes
Electronic Colloquium on Computational Complexity (ECCC) 8(36): (2001) |
| 2000 |
|---|
| 31 | | Sanjeev 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 |
|---|
| 29 | | Irit Dinur,
Eldar Fischer,
Guy Kindler,
Ran Raz,
Shmuel Safra:
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.
STOC 1999: 29-40 |
| 28 | | Irit Dinur,
Shmuel Safra:
On the Hardness of Approximating Label Cover
Electronic Colloquium on Computational Complexity (ECCC) 6(15): (1999) |
| 27 | | Oded 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) |
| 26 | | 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): 55-61 (1999) |
| 1998 |
|---|
| 25 | | Irit Dinur,
Guy Kindler,
Shmuel Safra:
Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard.
FOCS 1998: 99-111 |
| 24 | | Irit Dinur,
Guy Kindler,
Shmuel Safra:
Approximating CVP to Within Almost Polynomial Factor is NP-Hard
Electronic Colloquium on Computational Complexity (ECCC) 5(48): (1998) |
| 23 | | Irit 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) |
| 22 | | Sanjeev 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 |
| 19 | | Ran 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 |
| 17 | | Oded Goldreich,
Shmuel Safra:
A Combinatorial Consistency Lemma with application to the PCP Theorem
Electronic Colloquium on Computational Complexity (ECCC) 3(47): (1996) |
| 16 | | Uriel 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 |
|---|
| 15 | | Peter 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 |
|---|
| 10 | | Cynthia 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 |
