| 2005 | SODA | The complexity of low-distortion embeddings between point sets. | Christos H. Papadimitriou, Shmuel Safra |
| 2003 | ESA | On the Complexity of Approximating TSP with Neighborhoods and Related Problems. | Shmuel Safra, Oded Schwartz |
| 2003 | FOCS | Proving Hard-Core Predicates Using List Decoding. | Adi Akavia, Shafi Goldwasser, Shmuel Safra |
| 2002 | FOCS | Testing Juntas. | Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky |
| 2002 | STOC | On the complexity of equilibria. | Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra |
| 2002 | STOC | The importance of being biased. | Irit Dinur, Shmuel Safra |
| 2001 | FOCS | Extractors from Reed-Muller Codes. | Amnon Ta-Shma, David Zuckerman, Shmuel Safra |
| 1999 | STOC | PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. | Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra |
| 1998 | FOCS | Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard. | Irit Dinur, Guy Kindler, Shmuel Safra |
| 1997 | STOC | A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. | Ran Raz, Shmuel Safra |
| 1996 | LICS | Relating Word and Tree Automata. | Orna Kupferman, Shmuel Safra, Moshe Y. Vardi |
| 1995 | STOC | On data structures and asymmetric communication complexity. | Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson |
| 1992 | CRYPTO | Low Communication 2-Prover Zero-Knowledge Proofs for NP. | Cynthia Dwork, Uriel Feige, Joe Kilian, Moni Naor, Shmuel Safra |
| 1992 | FOCS | Probabilistic Checking of Proofs; A New Characterization of NP | Sanjeev Arora, Shmuel Safra |
| 1992 | STOC | Exponential Determinization for omega-Automata with Strong-Fairness Acceptance Condition (Extended Abstract) | Shmuel Safra |
| 1991 | FOCS | Approximating Clique is Almost NP-Complete (Preliminary Version) | Uriel Feige, Shafi Goldwasser, Lszl Lovsz, Shmuel Safra, Mario Szegedy |
| 1989 | STOC | On omega-Automata and Temporal Logic (Preliminary Report) | Shmuel Safra, Moshe Y. Vardi |
| 1988 | FOCS | On the Complexity of omega-Automata | Shmuel Safra |
| 1985 | ICPP | Fast Multiway Merge Using Destructive Operation. | Ehud Shapiro, Shmuel Safra |