| Probabilistic checking of proofs: A new characterization of NP S Arora, S Safra Journal of the ACM (JACM) 45 (1), 70-122, 1998 | 1917 | 1998 |
| A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP R Raz, S Safra Proceedings of the twenty-ninth annual ACM symposium on Theory of computing …, 1997 | 1111 | 1997 |
| On the complexity of omega-automata S Safra [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science …, 1988 | 1018* | 1988 |
| Approximating clique is almost NP-complete U Feige, S Goldwasser, L Lovász, S Safra, M Szegedy [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science …, 1991 | 632 | 1991 |
| Interactive proofs and the hardness of approximating cliques U Feige, S Goldwasser, L Lovász, S Safra, M Szegedy Journal of the ACM (JACM) 43 (2), 268-292, 1996 | 576 | 1996 |
| On data structures and asymmetric communication complexity PB Miltersen, N Nisan, S Safra, A Wigderson Proceedings of the twenty-seventh annual ACM symposium on Theory of …, 1995 | 402 | 1995 |
| Algorithmic construction of sets for k-restrictions N Alon, D Moshkovitz, S Safra ACM Transactions on Algorithms (TALG) 2 (2), 153-177, 2006 | 373 | 2006 |
| Approximating-CVP to within almost-polynomial factors is NP-hard I Dinur, G Kindler, S Safra Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat …, 1998 | 312 | 1998 |
| The importance of being biased I Dinur, S Safra Proceedings of the thiry-fourth annual ACM symposium on Theory of computing …, 2002 | 311 | 2002 |
| Approximating shortest lattice vectors is not harder than approximating closest lattice vectors O Goldreich, D Micciancio, S Safra, JP Seifert Information Processing Letters 71 (2), 55-61, 1999 | 241 | 1999 |
| On the complexity of approximating k-set packing E Hazan, S Safra, O Schwartz computational complexity 15 (1), 20-39, 2006 | 220 | 2006 |
| Testing juntas E Fischer, G Kindler, D Ron, S Safra, A Samorodnitsky Journal of Computer and System Sciences 68 (4), 753-787, 2004 | 180 | 2004 |
| On the hardness of approximating the chromatic number S Khanna, N Linial, S Safra Combinatorica 20 (3), 393-415, 2000 | 165 | 2000 |
| Pseudorandom sets in grassmann graph have near-perfect expansion K Subhash, D Minzer, M Safra 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS …, 2018 | 160 | 2018 |
| On the complexity of equilibria X Deng, C Papadimitriou, S Safra Proceedings of the thiry-fourth annual ACM symposium on Theory of computing …, 2002 | 156 | 2002 |
| Complexity of automata on infinite objects S Safra PhD thesis, The Weizmann Institute of Science, 1989 | 155 | 1989 |
| Proving hard-core predicates using list decoding A Akavia, S Goldwasser, S Safra FOCS 44, 146-159, 2003 | 143 | 2003 |
| Exponential determinization for ω-automata with strong-fairness acceptance condition S Safra Proceedings of the twenty-fourth annual ACM symposium on Theory of computing …, 1992 | 129 | 1992 |
| Meta interpreters for real S Safra, E Shapiro Concurrent Prolog: Collected Papers, 166-179, 1988 | 124 | 1988 |
| Extractors from reed–muller codes A Ta-Shma, D Zuckerman, S Safra Journal of Computer and System Sciences 72 (5), 786-812, 2006 | 116 | 2006 |
