| Proof verification and the hardness of approximation problems S Arora, C Lund, R Motwani, M Sudan, M Szegedy Journal of the ACM (JACM) 45 (3), 501-555, 1998 | 3309 | 1998 |
| The space complexity of approximating the frequency moments N Alon, Y Matias, M Szegedy Proceedings of the twenty-eighth annual ACM symposium on Theory of computing …, 1996 | 2742 | 1996 |
| Checking computations in polylogarithmic time L Babai, L Fortnow, LA Levin, M Szegedy Proceedings of the twenty-third annual ACM symposium on Theory of computing …, 1991 | 909 | 1991 |
| Quantum speed-up of Markov chain based algorithms M Szegedy 45th Annual IEEE symposium on foundations of computer science, 32-41, 2004 | 888 | 2004 |
| 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 | 613 | 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 | 606 | 1996 |
| Threshold circuits of bounded depth A Hajnal, W Maass, P Pudlák, M Szegedy, G Turán Journal of Computer and System Sciences 46 (2), 129-154, 1993 | 533 | 1993 |
| Quantum algorithms for the triangle problem F Magniez, M Santha, M Szegedy SIAM Journal on Computing 37 (2), 413-424, 2007 | 519 | 2007 |
| On the degree of Boolean functions as real polynomials N Nisan, M Szegedy Computational complexity 4 (4), 301-313, 1994 | 514 | 1994 |
| Efficient testing of large graphs N Alon, E Fischer, M Krivelevich, M Szegedy Combinatorica 20 (4), 451-476, 2000 | 499 | 2000 |
| Tracking join and self-join sizes in limited storage N Alon, PB Gibbons, Y Matias, M Szegedy Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on …, 1999 | 393 | 1999 |
| Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs L Babai, N Nisant, M Szegedy Journal of Computer and System Sciences 45 (2), 204-232, 1992 | 329 | 1992 |
| Regular languages are testable with a constant number of queries N Alon, M Krivelevich, I Newman, M Szegedy SIAM Journal on Computing 30 (6), 1842-1862, 2001 | 200 | 2001 |
| Applications of the crossing number J Pach, F Shahrokhi, M Szegedy Proceedings of the tenth annual symposium on Computational geometry, 198-202, 1994 | 199 | 1994 |
| Quantum query complexity of state conversion T Lee, R Mittal, BW Reichardt, R Špalek, M Szegedy 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, 344-353, 2011 | 195 | 2011 |
| Classical simulation of quantum supremacy circuits C Huang, F Zhang, M Newman, J Cai, X Gao, Z Tian, J Wu, H Xu, H Yu, ... arXiv preprint arXiv:2005.06787, 2020 | 172 | 2020 |
| Multiparty protocols and logspace-hard pseudorandom sequences L Babai, N Nisan, M Szegedy Proceedings of the twenty-first annual ACM symposium on Theory of computing …, 1989 | 141 | 1989 |
| Lower bounds for on-line graph coloring MM Halldórsson, M Szegedy Theoretical Computer Science 130 (1), 163-174, 1994 | 132 | 1994 |
| On the degree of Boolean functions as real polynomials N Nisan, M Szegedy Proceedings of the twenty-fourth annual ACM symposium on Theory of computing …, 1992 | 128 | 1992 |
| Public vs. private coin flips in one round communication games I Newman, M Szegedy Proceedings of the twenty-eighth annual ACM symposium on Theory of computing …, 1996 | 125 | 1996 |
Noga AlonPrinceton University and Tel Aviv UniversityVerified email at tau.ac.il
