Mario Szegedy - Google Scholar

Cited by

	All	Since 2015
Citations	11792	3416
h-index	38	25
i10-index	73	45

700

350

175

525

19911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202031 83 117 219 223 247 208 243 201 211 201 242 316 343 475 506 576 480 526 543 500 535 565 588 538 576 555 560 692 494

Co-authors

Noga AlonPrinceton University and Tel Aviv UniversityVerified email at tau.ac.il
Laszlo Lovaszprofessor of mathematics, Eotvos University, BudapestVerified email at cs.elte.hu
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
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
Janos PachEcole Polytechnique Federale de Lausanne and Renyi Institute BudapestVerified email at renyi.hu
Noam NisanProfessor of Computer Science, Hebrew University of JerusalemVerified email at cs.huji.ac.il
Michael KrivelevichProfessor of Mathematics, Tel Aviv UniversityVerified email at post.tau.ac.il
Magnús M. HalldórssonProfessor of Computer Science, Reykjavik UniversityVerified email at ru.is
Robert SpalekundisclosedVerified email at ucw.cz
Leonid A. LevinVerified email at bu.edu
Ilan NewmanProfessor of Computer Science, University of HaifaVerified email at cs.haifa.ac.il
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	2631	1998
The space complexity of approximating the frequency moments N Alon, Y Matias, M Szegedy Journal of Computer and system sciences 58 (1), 137-147, 1999	1996	1999
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	682	1991
Approximating clique is almost NP-complete U Feige, S Goldwasser, L Lovász, S Safra, M Szegedy Proc. 32nd IEEE Symp. on Foundations of Computer Science, 2-12, 1991	550	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	476	1996
Quantum speed-up of Markov chain based algorithms M Szegedy 45th Annual IEEE symposium on foundations of computer science, 32-41, 2004	475	2004
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	432	1993
Efficient testing of large graphs N Alon, E Fischer, M Krivelevich, M Szegedy Combinatorica 20 (4), 451-476, 2000	384	2000
On the degree of Boolean functions as real polynomials N Nisan, M Szegedy Computational complexity 4 (4), 301-313, 1994	350	1994
Quantum algorithms for the triangle problem F Magniez, M Santha, M Szegedy SIAM Journal on Computing 37 (2), 413-424, 2007	349	2007
Tracking join and self-join sizes in limited storage N Alon, PB Gibbons, Y Matias, M Szegedy Journal of Computer and System Sciences 64 (3), 719-747, 2002	297	2002
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	276	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	166	2001
Applications of the crossing number J Pach, F Shahrokhi, M Szegedy Algorithmica 16 (1), 111-117, 1996	158	1996
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	130	1989
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	116	2011
Lower bounds for on-line graph coloring MM Halldórsson, M Szegedy Theoretical Computer Science 130 (1), 163-174, 1994	113	1994
On Conway's thrackle conjecture L Lovász, J Pach, M Szegedy Discrete & Computational Geometry 18 (4), 369-376, 1997	104	1997
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	100	1996
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	98	1992

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

Upload PDF

Follow this author

Cited by

Co-authors