M. Szegedy

Most-cited papers

Efficient Testing of Large Graphs
N. Alon, Eldar Fischer, Michael Krivelevich, M. Szegedy
200040th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)396 citations
Semantic Scholar
Quantum algorithms for the triangle problem
F. Magniez, M. Santha, M. Szegedy
2003ACM-SIAM Symposium on Discrete Algorithms386 citations Open access
Semantic Scholar
Tracking join and self-join sizes in limited storage
N. Alon, Phillip B. Gibbons, Yossi Matias, M. Szegedy
1999Journal of computer and system sciences (Print)320 citations Open access
Semantic Scholar
Quantum Query Complexity of State Conversion
Troy Lee, R. Mittal, B. Reichardt, R. Spałek +1 more
2010IEEE Annual Symposium on Foundations of Computer Science182 citations Open access
Semantic Scholar
Classical Simulation of Quantum Supremacy Circuits
Cupjin Huang, Fang Zhang, M. Newman, Junjie Cai +9 more
2020154 citations
Semantic Scholar
Hardness of Approximation
M. Szegedy
2007Handbook of Approximation Algorithms and Metaheuristics149 citations
Semantic Scholar
Finding Angles for Quantum Signal Processing with Machine Precision.
Rui Chao, Dawei Ding, A. Gilyén, Cupjin Huang +1 more
2020111 citations
Semantic Scholar
Quantum query complexity and semi-definite programming
H. Barnum, M. Saks, M. Szegedy
200318th IEEE Annual Conference on Computational Complexity, 2003. Proceedings.101 citations
Semantic Scholar
Moser and tardos meet Lovász
K. Kolipaka, M. Szegedy
2011Symposium on the Theory of Computing98 citations Open access
Semantic Scholar
Efficient parallelization of tensor network contraction for simulating quantum computation
Cupjin Huang, Fang Zhang, M. Newman, Xiaotong Ni +17 more
2021Nature Computational Science91 citations Open access
Semantic Scholar
THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS
Sophie Laplante, Troy Lee, M. Szegedy
2005Cybersecurity and Cyberforensics Conference77 citations Open access
Semantic Scholar
Learning Mixtures of Ranking Models
Pranjal Awasthi, Eric Allender, M. Saks, M. Szegedy
2014Neural Information Processing Systems69 citations
Semantic Scholar
Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
Xiao-Min Chen, J. Pach, M. Szegedy, G. Tardos
2008ACM-SIAM Symposium on Discrete Algorithms68 citations Open access
Semantic Scholar
A new line of attack on the dichotomy conjecture
G. Kun, M. Szegedy
2009Symposium on the Theory of Computing53 citations Open access
Semantic Scholar
The DLT priority sampling is essentially optimal
M. Szegedy
2006Symposium on the Theory of Computing50 citations
Semantic Scholar
Quantum Decision Trees and Semidefinite Programming.
H. Barnum, M. Saks, M. Szegedy
200149 citations
Semantic Scholar
What are the least tractable instances of max independent set?
David S. Johnson, M. Szegedy
1999ACM-SIAM Symposium on Discrete Algorithms46 citations
Semantic Scholar
Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis
Matthias Poloczek, M. Szegedy
2012IEEE Annual Symposium on Foundations of Computer Science44 citations
Semantic Scholar
Parent-Identifying Codes
N. Alon, Eldar Fischer, M. Szegedy
2001Journal of Combinatorial Theory43 citations Open access
Semantic Scholar
A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing
Ling-Da Li, Robel Geda, Ari B. Hayes, Yan-Hao Chen +3 more
2017Measurement and Modeling of Computer Systems42 citations
Semantic Scholar
A Sharper Local Lemma with Improved Applications
K. Kolipaka, M. Szegedy, Yixin Xu
2012International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques42 citations
Semantic Scholar
In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved?
M. Szegedy
1999Symposium on Theoretical Aspects of Computer Science42 citations
Semantic Scholar
An $O(n^{1.3})$ Quantum Algorithm for the Triangle Problem
F. Magniez, M. Santha, M. Szegedy
200339 citations
Semantic Scholar
Mechanism design: from partial to probabilistic verification
I. Caragiannis, Edith Elkind, M. Szegedy, Lan Yu
2012ACM Conference on Economics and Computation38 citations
Semantic Scholar
Explicit Lower Bounds on Strong Quantum Simulation
Cupjin Huang, M. Newman, M. Szegedy
2018IEEE Transactions on Information Theory37 citations Open access
Semantic Scholar
Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law
D. Aharonov, A. Harrow, Zeph Landau, Daniel Nagaj +2 more
2014IEEE Annual Symposium on Foundations of Computer Science36 citations Open access
Semantic Scholar
Classical simulation of entanglement swapping with bounded communication.
C. Branciard, N. Brunner, H. Buhrman, R. Cleve +4 more
2012Physical Review Letters29 citations Open access
Semantic Scholar
Streaming and Communication Complexity of Clique Approximation
M. Halldórsson, Xiao-Ming Sun, M. Szegedy, Chen-Gu Wang
2012International Colloquium on Automata, Languages and Programming29 citations
Semantic Scholar
Quantum and Classical Query Complexities of Local Search Are Polynomially Related
M. Santha, M. Szegedy
2004Symposium on the Theory of Computing29 citations
Semantic Scholar
Streaming Algorithms for Independent Sets
B. Halldórsson, M. Halldórsson, Elena Losievskaja, M. Szegedy
2010International Colloquium on Automata, Languages and Programming27 citations
Semantic Scholar
Spectra of Quantized Walks and a $\sqrt{\delta\epsilon}$ rule
M. Szegedy
200426 citations
Semantic Scholar
testing of large graphs
N. Alon, Eldar Fischer, Michael Krivelevich, M. Szegedy
200026 citations
Semantic Scholar
Many-Valued Logics and Holographic Proofs
M. Szegedy
1999International Colloquium on Automata, Languages and Programming26 citations
Semantic Scholar
What do QAOA energies reveal about graphs
M. Szegedy
201925 citations
Semantic Scholar
Product Rules in Semidefinite Programming
R. Mittal, M. Szegedy
2007International Symposium on Fundamentals of Computation Theory25 citations
Semantic Scholar
The Lovász Local Lemma - A Survey
M. Szegedy
2013Computer Science Symposium in Russia24 citations
Semantic Scholar
On the Quantum Query Complexity of Detecting Triangles in Graphs
M. Szegedy
200324 citations
Semantic Scholar
Large Sets of Nearly Orthogonal Vectors
N. Alon, M. Szegedy
1999Graphs Comb.24 citations
Semantic Scholar
Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design
Cupjin Huang, M. Szegedy, Fang Zhang, Xun Gao +2 more
201922 citations
Semantic Scholar
Geometric representation of cubic graphs with four directions
Padmini Mukkamala, M. Szegedy
2009Computational geometry21 citations Open access
Semantic Scholar
Generating k EPR-pairs from an n-party resource state
S. Bravyi, Yash Sharma, M. Szegedy, Ronald de Wolf
2022Quantum19 citations Open access
Semantic Scholar
Streaming Algorithms for Independent Sets in Sparse Hypergraphs
B. Halldórsson, M. Halldórsson, Elena Losievskaja, M. Szegedy
2016Algorithmica19 citations
Semantic Scholar
Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions
Eike Kiltz, Krzysztof Pietrzak, M. Szegedy
2013Annual International Cryptology Conference18 citations
Semantic Scholar
Repeated Averages on Graphs
R. Movassagh, M. Szegedy, Guanyang Wang
2022The Annals of Applied Probability17 citations Open access
Semantic Scholar
Long Monotone Paths in Line Arrangements
J. Balogh, O. Regev, Clifford D. Smyth, W. Steiger +1 more
2003SCG '0316 citations Open access
Semantic Scholar
Alibaba Cloud Quantum Development Platform: Large-Scale Classical Simulation of Quantum Circuits
Fang Zhang, Cupjin Huang, M. Newman, Junjie Cai +9 more
201915 citations
Semantic Scholar
Computing Boolean functions from multiple faulty copies of input bits
M. Szegedy, Xiao-Min Chen
2002Theoretical Computer Science15 citations Open access
Semantic Scholar
On the Variance of Subset Sum Estimation
M. Szegedy, M. Thorup
2007Embedded Systems and Applications14 citations Open access
Semantic Scholar
Quantum advantage for combinatorial optimization problems, Simplified
M. Szegedy
202213 citations
Semantic Scholar
The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry)
Jan Dean Catarata, S. Corbett, Harry Stern, M. Szegedy +2 more
2017Workshop on Algorithm Engineering and Experimentation12 citations
Semantic Scholar