Mario Szegedy | Academic Influence

Mario Szegedy's AcademicInfluence.com Rankings

Mario Szegedy

Computer Science

#600

World Rank

#620

Historical Rank

#326

USA Rank

Machine Learning

#1838

World Rank

#1862

Historical Rank

#125

USA Rank

computer-science Degrees

Mario Szegedy

Mathematics

#967

World Rank

#1673

Historical Rank

#422

USA Rank

Measure Theory

#2519

World Rank

#3025

Historical Rank

#713

USA Rank

mathematics Degrees

Download Badge

Computer Science
Mathematics

Mario Szegedy's Degrees

PhD Computer Science Eötvös Loránd University
Masters Mathematics Eötvös Loránd University

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Mario Szegedy Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Mario Szegedy is a Hungarian-American computer scientist, professor of computer science at Rutgers University. He received his Ph.D. in computer science in 1989 from the University of Chicago. He held a Lady Davis Postdoctoral Fellowship at the Hebrew University of Jerusalem , a postdoc at the University of Chicago, 1991–92, and a postdoc at Bell Laboratories .

(See a Problem?)

Mario Szegedy's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Proof verification and hardness of approximation problems (1992) (2163)
The space complexity of approximating the frequency moments (1996) (2003)
Checking computations in polylogarithmic time (1991) (625)
Quantum speed-up of Markov chain based algorithms (2004) (625)
On the degree of boolean functions as real polynomials (1992) (484)
Approximating clique is almost NP-complete (1991) (468)
Interactive proofs and the hardness of approximating cliques (1996) (465)
Threshold circuits of bounded depth (1987) (407)
Efficient Testing of Large Graphs (2000) (360)
Quantum algorithms for the triangle problem (2003) (343)
Tracking join and self-join sizes in limited storage (1999) (298)
Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs (1992) (270)
Regular languages are testable with a constant number of queries (1999) (156)
Quantum Query Complexity of State Conversion (2010) (146)
All Quantum Adversary Methods are Equivalent (2004) (124)
Multiparty protocols and logspace-hard pseudorandom sequences (1989) (123)
Applications of the crossing number (1994) (118)
Lower bounds for on-line graph coloring (1992) (107)
Moser and tardos meet Lovász (2011) (93)
On Conway's Thrackle Conjecture (1995) (92)
Quantum query complexity and semi-definite programming (2003) (92)
Locality based graph coloring (1993) (91)
A note on the /spl theta/ number of Lovasz and the generalized Delsarte bound (1994) (79)
THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS (2005) (74)
Classical Simulation of Quantum Supremacy Circuits (2020) (69)
Public vs. private coin flips in one round communication games (extended abstract) (1996) (65)
Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles (2008) (56)
Local Expansion of Symmetrical Graphs (1992) (53)
A new line of attack on the dichotomy conjecture (2009) (52)
A New Lower Bound Theorem for Read-Only-Once Branching Programs and its Applications (1992) (48)
Algorithms to tile the infinite grid with finite clusters (1998) (47)
Quantum Decision Trees and Semidefinite Programming. (2001) (46)
The DLT priority sampling is essentially optimal (2006) (46)
Parent-Identifying Codes (2001) (44)
What are the least tractable instances of max independent set? (1999) (43)
In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved? (1999) (41)
An $O(n^{1.3})$ Quantum Algorithm for the Triangle Problem (2003) (39)
A Sharper Local Lemma with Improved Applications (2012) (39)
Finding Angles for Quantum Signal Processing with Machine Precision. (2020) (37)
Mechanism design: from partial to probabilistic verification (2012) (37)
Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis (2012) (36)
Explicit Lower Bounds on Strong Quantum Simulation (2018) (29)
Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law (2014) (28)
Product Rules in Semidefinite Programming (2007) (27)
The Lovász Local Lemma - A Survey (2013) (26)
Many-Valued Logics and Holographic Proofs (1999) (26)
Spectra of Quantized Walks and a $\sqrt{\delta\epsilon}$ rule (2004) (26)
A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing (2017) (25)
Streaming Algorithms for Independent Sets (2010) (25)
testing of large graphs (2000) (24)
On the Quantum Query Complexity of Detecting Triangles in Graphs (2003) (24)
Classical simulation of entanglement swapping with bounded communication. (2012) (23)
Streaming and Communication Complexity of Clique Approximation (2012) (21)
Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions (2013) (20)
Geometric representation of cubic graphs with four directions (2009) (20)
Quantum and Classical Query Complexities of Local Search Are Polynomially Related (2004) (20)
Efficient parallelization of tensor network contraction for simulating quantum computation (2021) (18)
Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design (2019) (18)
The solution of graham’s greatest common divisor problem (1986) (17)
Functions with Bounded Symmetric Communication Complexity, Programs over Commutative Monoids, and ACC (1993) (17)
What do QAOA energies reveal about graphs (2019) (17)
Large Sets of Nearly Orthogonal Vectors (1999) (16)
Fault tolerant circuits and probabilistically checkable proofs (1995) (16)
Computing Boolean functions from multiple faulty copies of input bits (2002) (15)
Long Monotone Paths in Line Arrangements (2003) (14)
Functions with bounded symmetric communication complexity and circuits with mod m gates (1990) (14)
Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles (2009) (13)
On the Power of Two-Local Random Reductions (1991) (13)
On packing bipartite graphs (1992) (13)
On the Variance of Subset Sum Estimation (2007) (13)
Alibaba Cloud Quantum Development Platform: Large-Scale Classical Simulation of Quantum Circuits (2019) (13)
Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract) (1989) (12)
A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing (2017) (12)
Streaming Algorithms for Independent Sets in Sparse Hypergraphs (2016) (12)
On the complexity of RAM with various operation sets (1992) (11)
Languages with Bounded Multiparty Communication Complexity (2007) (10)
Just the fax—differentiating voice and fax phone lines using call billing data (1999) (8)
On Rearrangement of Items Stored in Stacks (2020) (8)
The Garden Hose Complexity for the Equality Function (2013) (8)
The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry) (2017) (7)
Query Complexity (7)
Near optimality of the priority sampling procedure (2005) (7)
Impossibility Theorems and the Universal Algebraic Toolkit (2015) (7)
An O(n0.4732) upper bound on the complexity of the GKS communication game (2015) (7)
Alibaba Cloud Quantum Development Kit: Large-Scale Classical Simulation of Quantum Circuits (2019) (6)
The number of simplices embracing the origin (2003) (6)
Explicit lower bounds on strong simulation of quantum circuits in terms of $T$-gate count (2019) (6)
Quantum Algorithm for the Triangle Problem (2003) (6)
On-line complexity of monotone set systems (1999) (5)
Spectra of Quantized Walks and a √ δε -Rule (2022) (5)
Six-way equipartitioning by three lines in the plane (2010) (5)
The Telephone Problem for Connected Graphs (1984) (4)
Parallel Repetition of the Odd Cycle Game (2008) (4)
Amortized Communication Complexity of Distributions (2009) (4)
Quantum advantage for combinatorial optimization problems, Simplified (2022) (2)
Approximating Clique is Almost NP-Complete (Preliminary Version) (1991) (2)
Quantum Locally Testable Code with Exotic Parameters (2022) (2)
On the communication complexity of distributions (2008) (2)
Probabilistic Verification and Non-Approximability (2004) (2)
Rubik Tables and object rearrangement (2020) (2)
Digital Signatures with Minimal Overhead (2012) (1)
Hardness of Approximation (2007) (1)
a (mod p ) ≤ 9T b (mod p ) for all primes p implies a = b (1987) (1)
Repeated Averages on Graphs (2022) (1)
A subset coloring algorithm and its applications to computer graphics (1988) (1)
The Interaction Light Cone of the Discrete Bak–Sneppen, Contact and other local processes (2019) (1)
A Dichotomy Theorem for Typed Constraint Satisfaction Problems (2006) (1)
Quantum Analogues of Markov Chains (2016) (1)
A Graph-based Model for GPU Caching Problems (2016) (1)
Optimally Balanced Forward Degree Sequence (2005) (1)
Quantization of Markov Chains (2008) (1)
Quantum walks and ground state problems (2007) (1)
UvA-DARE (Digital Academic Repository) Classical simulation of entanglement swapping with bounded communication Branciard, (2012) (0)
OBSTACLES, SLOPES AND TIC-TAC-TOE: AN EXCURSION IN DISCRETE GEOMETRY AND COMBINATORIAL GAME THEORY (2011) (0)
A simplified proof of a Lee-Yang type theorem (2014) (0)
Combinatorics, Groups, Algorithms, and Complexity: Conference in honor of Laci Babai's 60th birthday (2011) (0)
Generating $k$ EPR-pairs from an n-party resource state (2022) (0)
Application of sdp to product rules and quantum query complexity (2011) (0)
A clique size bounding technique with application to non-linear codes (1999) (0)
CKit: A Preprocessor for Algorithmic Experiments (2008) (0)
Title : Quantum Analogues of Markov Chains (2015) (0)
Lower Bounds for On-line Graph Coloring Magn us M. Halld orsson (2016) (0)
Proceedings Twenty-Second Annual IEEE Conference on Computational Complexity: Preface (2007) (0)
Streaming Algorithms for Independent Sets in Sparse Hypergraphs (2015) (0)
Budgeted Steiner Networks: Three Terminals with Equal Path Weights (2022) (0)
Rubik Tables, Stack Rearrangement, and Multi-Robot Path Planning (2022) (0)
Problems in discrete geometry (2006) (0)
CKit : A Preprocessor for Algorithmic Experiments (Algorithm Engineering as a New Paradigm) (2001) (0)

This paper list is powered by the following services:

Other Resources About Mario Szegedy

en.wikipedia.org

What Schools Are Affiliated With Mario Szegedy?

Mario Szegedy is affiliated with the following schools:

Image Attributions

Image Source for Mario Szegedy