Mario Szegedy

Cited by

	All	Since 2018
Citations	14156	3824
h-index	41	27
i10-index	78	51

720

360

180

540

19911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202338 86 126 241 248 242 223 265 203 211 225 256 321 347 467 501 587 496 532 549 493 528 567 603 537 608 554 544 678 674 660 702 566

Public access

View all

10 articles

0 articles

available

not available

Based on funding mandates

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
Miklos SanthaSenior researcher in Computer Science, CNRS Paris and CQT SingaporeVerified email at liafa.univ-paris-diderot.fr
Lance FortnowIllinois Institute of TechnologyVerified email at iit.edu
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	3004	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	2429	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	811	1991
Quantum speed-up of Markov chain based algorithms M Szegedy 45th Annual IEEE symposium on foundations of computer science, 32-41, 2004	681	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	605	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	539	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	501	1993
On the degree of Boolean functions as real polynomials N Nisan, M Szegedy Computational complexity 4, 301-313, 1994	455	1994
Efficient testing of large graphs N Alon, E Fischer, M Krivelevich, M Szegedy Combinatorica 20 (4), 451-476, 2000	444	2000
Quantum algorithms for the triangle problem F Magniez, M Santha, M Szegedy SIAM Journal on Computing 37 (2), 413-424, 2007	428	2007
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	353	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	316	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	190	2001
Applications of the crossing number J Pach, F Shahrokhi, M Szegedy Proceedings of the tenth annual symposium on Computational geometry, 198-202, 1994	180	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	160	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	139	1989
Lower bounds for on-line graph coloring MM Halldórsson, M Szegedy Theoretical Computer Science 130 (1), 163-174, 1994	125	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	117	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	116	1992
On Conway's thrackle conjecture L Lovász Proceedings of the eleventh annual symposium on Computational geometry, 147-151, 1995	108	1995

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