Mario Szegedy

Cited by

	All	Since 2016
Citations	12802	3636
h-index	40	26
i10-index	76	48

700

350

175

525

19921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202188 120 240 247 250 229 270 208 213 216 252 321 338 462 506 595 481 553 549 502 534 567 594 543 602 543 556 671 699 564

Public access

View all

8 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
Laszlo Lovaszprofessor of mathematics, Eotvos University, BudapestVerified email at cs.elte.hu
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	2799	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	2187	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	720	1991
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	566	1991
Quantum speed-up of Markov chain based algorithms M Szegedy 45th Annual IEEE symposium on foundations of computer science, 32-41, 2004	541	2004
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	498	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	461	1993
Efficient testing of large graphs N Alon, E Fischer, M Krivelevich, M Szegedy Combinatorica 20 (4), 451-476, 2000	406	2000
On the degree of Boolean functions as real polynomials N Nisan, M Szegedy Computational complexity 4 (4), 301-313, 1994	390	1994
Quantum algorithms for the triangle problem F Magniez, M Santha, M Szegedy SIAM Journal on Computing 37 (2), 413-424, 2007	377	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	329	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	297	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	180	2001
Applications of the crossing number J Pach, F Shahrokhi, M Szegedy Algorithmica 16 (1), 111-117, 1996	171	1996
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	133	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	132	1989
Lower bounds for on-line graph coloring MM Halldórsson, M Szegedy Theoretical Computer Science 130 (1), 163-174, 1994	119	1994
On Conway's thrackle conjecture L Lovász, J Pach, M Szegedy Discrete & Computational Geometry 18 (4), 369-376, 1997	108	1997
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	108	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	107	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 this author

Cited by

Co-authors