Mario Szegedy

Cited by

	All	Since 2019
Citations	15009	4069
h-index	43	27
i10-index	78	51

780

390

195

585

199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202438 87 136 243 252 256 223 270 210 209 214 259 325 341 456 501 593 500 530 555 506 528 574 601 533 609 549 547 668 669 643 682 772 632

Public access

View all

13 articles

0 articles

available

not available

Based on funding mandates

Co-authors

Noga AlonPrinceton University and Tel Aviv UniversityVerified email at tau.ac.il
Madhu SudanGordon McKay Professor of Computer Science, Harvard UniversityVerified email at cs.harvard.edu
Sanjeev AroraProfessor of Computer Science, Princeton UniversityVerified email at cs.princeton.edu
Yossi MatiasGoogleVerified email at tau.ac.il
Laszlo Lovaszprofessor of mathematics, Eotvos University, BudapestVerified email at cs.elte.hu
Lance FortnowIllinois Institute of TechnologyVerified email at iit.edu
Miklos SanthaSenior researcher in Computer Science, CNRS Paris and CQT SingaporeVerified email at liafa.univ-paris-diderot.fr
Noam NisanProfessor of Computer Science, Hebrew University of JerusalemVerified email at cs.huji.ac.il
Robert SpalekundisclosedVerified email at ucw.cz
Janos PachEcole Polytechnique Federale de Lausanne and Renyi Institute BudapestVerified email at renyi.hu
Michael KrivelevichProfessor of Mathematics, Tel Aviv UniversityVerified email at post.tau.ac.il
Ilan NewmanProfessor of Computer Science, University of HaifaVerified email at cs.haifa.ac.il
Magnús M. HalldórssonProfessor of Computer Science, Reykjavik UniversityVerified email at ru.is
Leonid A. LevinVerified email at bu.edu
Wolfgang MaassProfessor of Computer Science, Graz University of TechnologyVerified email at igi.tugraz.at
Gyorgy Turan University of Illinois at Chicago, and Hungarian Academy of SciencesVerified email at uic.edu

Mario Szegedy

Professor of Computer Science, Rutgers University

Verified email at cs.rutgers.edu - Homepage

Complexity Theory Combinatorics Quantum Computing Geometry


Title Sort by citations Sort by year Sort by title	Cited by Cited by	Year
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	3129	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	2560	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	852	1991
Quantum speed-up of Markov chain based algorithms M Szegedy 45th Annual IEEE symposium on foundations of computer science, 32-41, 2004	773	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	622	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	553	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	518	1993
Quantum algorithms for the triangle problem F Magniez, M Santha, M Szegedy SIAM Journal on Computing 37 (2), 413-424, 2007	477	2007
Efficient testing of large graphs N Alon, E Fischer, M Krivelevich, M Szegedy Combinatorica 20 (4), 451-476, 2000	465	2000
On the degree of Boolean functions as real polynomials N Nisan, M Szegedy Computational complexity 4, 301-313, 1994	465	1994
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	367	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	326	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	196	2001
Applications of the crossing number J Pach, F Shahrokhi, M Szegedy Proceedings of the tenth annual symposium on Computational geometry, 198-202, 1994	191	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	170	2011
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	144	1989
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	140	2020
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	133	1992
Lower bounds for on-line graph coloring MM Halldórsson, M Szegedy Theoretical Computer Science 130 (1), 163-174, 1994	129	1994
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	118	1996

The system can't perform the operation now. Try again later.

Articles 1–20

Citations per year

Duplicate citations

Merged citations

Add co-authorsCo-authors

Follow

Cited by

Co-authors