The Telephone Problem for Connected Graphs. - Gustav Burosch; Waleri Wassiljewitsch Gorlow; Roger Labahn; Mario Szegedy (J. Inf. Process. Cybern., 1984)

The solution of Graham's greatest common divisor problem. - Mario Szegedy (Comb., 1986)

A Subset Coloring Algorithm and Its Applications to Computer Graphics. - David Rubinstein; Jeffrey O. Shallit; Mario Szegedy (Commun. ACM, 1988)

Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract) - László Babai; Noam Nisan; Mario Szegedy (STOC, 1989)

A New Lower Bound Theorem for Read-Only-Once Branching Programs and its Applications. - Janos Simon; Mario Szegedy (Advances In Computational Complexity Theory, 1990)

Functions with Bounded Symmetric Communication Complexity and Circuits with mathop mod m Gates - Mario Szegedy (STOC, 1990)

Approximating Clique is Almost NP-Complete (Preliminary Version) - Uriel Feige; Shafi Goldwasser; László Lovász 001; Shmuel Safra; Mario Szegedy (FOCS, 1991)

Checking Computations in Polylogarithmic Time - László Babai; Lance Fortnow; Leonid A. Levin; Mario Szegedy (STOC, 1991)

On the Complexity of RAM with Various Operation Sets - Janos Simon; Mario Szegedy (STOC, 1992)

On packing bipartite graphs. - Péter Hajnal; Mario Szegedy (Comb., 1992)

Local Expansion of Ssymmetrical Graphs. - László Babai; Mario Szegedy (Comb. Probab. Comput., 1992)

On the Power of Two-Local Random Reductions. - Lance Fortnow; Mario Szegedy (Inf. Process. Lett., 1992)

Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs. - László Babai; Noam Nisan; Mario Szegedy (J. Comput. Syst. Sci., 1992)

Locality based graph coloring. - Mario Szegedy; Sundar Vishwanathan (STOC, 1993)

Threshold Circuits of Bounded Depth. - András Hajnal; Wolfgang Maass 001; Pavel Pudlák; Mario Szegedy; György Turán (J. Comput. Syst. Sci., 1993)

Functions with Bounded Symmetric Communication Complexity, Programs over Commutative Monoids, and ACC. - Mario Szegedy (J. Comput. Syst. Sci., 1993)

A note on the Theta number of Lovász and the generalized Delsarte bound - Mario Szegedy (FOCS, 1994)

On the Degree of Boolean Functions as Real Polynomials. - Noam Nisan; Mario Szegedy (Comput. Complex., 1994)

Lower Bounds for On-Line Graph Coloring. - Magnús M. Halldórsson; Mario Szegedy (Theor. Comput. Sci., 1994)

Fault Tolerant Circuits and Probabilistically Checkable Proofs. - Anna Gál; Mario Szegedy (SCT, 1995)

Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). - Ilan Newman; Mario Szegedy (STOC, 1996)

Applications of the Crossing Number. - János Pach; Farhad Shahrokhi; Mario Szegedy (Algorithmica, 1996)

Interactive Proofs and the Hardness of Approximating Cliques. - Uriel Feige; Shafi Goldwasser; László Lovász 001; Shmuel Safra; Mario Szegedy (J. ACM, 1996)

On Conway's Thrackle Conjecture. - László Lovász 001; János Pach; Mario Szegedy (Discret. Comput. Geom., 1997)

Algorithms to Tile the Infinite Grid with Finite Clusters. - Mario Szegedy (FOCS, 1998)

Proof verification and the hardness of approximation problems. - Sanjeev Arora; Carsten Lund; Rajeev Motwani 001; Madhu Sudan 001; Mario Szegedy (Electron. Colloquium Comput. Complex., 1998)

Many-Valued Logics and Holographic Proofs. - Mario Szegedy (ICALP, 1999)

What are the Least Tractable Instances of max Independent Set? - David S. Johnson 001; Mario Szegedy (SODA, 1999)

On-line Complexity of Monotone Set Systems. - Haim Kaplan; Mario Szegedy (SODA, 1999)

Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data. - Haim Kaplan; Martin Strauss 001; Mario Szegedy (SODA, 1999)

A Slique Size Bounding Technique with Application to Non-Linear Codes. - Mario Szegedy (SODA, 1999)

In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved? - Mario Szegedy (STACS, 1999)

Large Sets of Nearly Orthogonal Vectors. - Noga Alon; Mario Szegedy (Graphs Comb., 1999)

The Space Complexity of Approximating the Frequency Moments. - Noga Alon; Yossi Matias; Mario Szegedy (J. Comput. Syst. Sci., 1999)

Efficient Testing of Large Graphs. - Noga Alon; Eldar Fischer; Michael Krivelevich; Mario Szegedy (Comb., 2000)

Regular Languages are Testable with a Constant Number of Queries. - Noga Alon; Michael Krivelevich; Ilan Newman; Mario Szegedy (SIAM J. Comput., 2000)

Parent-Identifying Codes. - Noga Alon; Eldar Fischer; Mario Szegedy (J. Comb. Theory A, 2001)

Tracking Join and Self-Join Sizes in Limited Storage. - Noga Alon; Phillip B. Gibbons; Yossi Matias; Mario Szegedy (J. Comput. Syst. Sci., 2002)

Quantum query complexity and semi-definite programming. - Howard Barnum; Michael E. Saks; Mario Szegedy (CCC, 2003)

Quantum Speed-Up of Markov Chain Based Algorithms. - Mario Szegedy (FOCS, 2004)

Long Monotone Paths in Line Arrangements. - József Balogh; Oded Regev 001; Clifford D. Smyth; William L. Steiger; Mario Szegedy (Discret. Comput. Geom., 2004)

Computing Boolean functions from multiple faulty copies of input bits. - Mario Szegedy; Xiaomin Chen (Theor. Comput. Sci., 2004)

Optimally Balanced Forward Degree Sequence. - Xiaomin Chen; Mario Szegedy; Lei Wang 039 (COCOON, 2005)

Near optimality of the priority sampling procedure - Mario Szegedy (Electron. Colloquium Comput. Complex., 2005)

A Dichotomy Theorem for Typed Constraint Satisfaction Problems. - Su Chen; Tomasz Imielinski; Karin Johnsgard; Donald Smith; Mario Szegedy (SAT, 2006)

The DLT priority sampling is essentially optimal. - Mario Szegedy (STOC, 2006)

The Quantum Adversary Method and Classical Formula Size Lower Bounds. - Sophie Laplante; Troy Lee; Mario Szegedy (Comput. Complex., 2006)

Languages with Bounded Multiparty Communication Complexity. - Arkadev Chattopadhyay; Michal Koucký 001; Andreas Krebs; Mario Szegedy; Pascal Tesson; Denis Thérien (Electron. Colloquium Comput. Complex., 2006)

All Quantum Adversary Methods are Equivalent. - Robert Spalek; Mario Szegedy (Theory Comput., 2006)

On the Variance of Subset Sum Estimation. - Mario Szegedy; Mikkel Thorup (ESA, 2007)

Product Rules in Semidefinite Programming. - Rajat Mittal 001; Mario Szegedy (FCT, 2007)

Quantum Algorithms for the Triangle Problem. - Frédéric Magniez; Miklos Santha; Mario Szegedy (SIAM J. Comput., 2007)

Hardness of Approximation. - Mario Szegedy (Handbook of Approximation Algorithms and Metaheuristics, 2007)

Parallel Repetition of the Odd Cycle Game. - Kooshiar Azimian; Mario Szegedy (LATIN, 2008)

Quantization of Markov Chains. - Peter C. Richter; Mario Szegedy (Encyclopedia of Algorithms, 2008)

Amortized Communication Complexity of Distributions. - Jérémie Roland; Mario Szegedy (ICALP (1), 2009)

Quantum and Classical Query Complexities of Local Search Are Polynomially Related. - Miklos Santha; Mario Szegedy (Algorithmica, 2009)

Geometric representation of cubic graphs with four directions. - Padmini Mukkamala; Mario Szegedy (Comput. Geom., 2009)

A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE. - Gábor Kun; Mario Szegedy (Electron. Colloquium Comput. Complex., 2009)

Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. - Xiaomin Chen; János Pach; Mario Szegedy; Gábor Tardos (Random Struct. Algorithms, 2009)

Six-way equipartitioning by three lines in the plane. - William Steiger; Mario Szegedy; Jihui Zhao (CCCG, 2010)

Streaming Algorithms for Independent Sets. - Bjarni V. Halldórsson; Magnús M. Halldórsson; Elena Losievskaja; Mario Szegedy (ICALP (1), 2010)

Quantum Query Complexity of State Conversion. - Troy Lee; Rajat Mittal 001; Ben W. Reichardt; Robert Spalek; Mario Szegedy (FOCS, 2011)

Moser and tardos meet Lovász. - Kashyap Babu Rao Kolipaka; Mario Szegedy (STOC, 2011)

Combinatorics, Groups, Algorithms, and Complexity: Conference in honor of Laci Babai's 60th birthday. - Ákos Seress; Mario Szegedy (Discret. Math. Theor. Comput. Sci., 2011)

A Sharper Local Lemma with Improved Applications. - Kashyap Babu Rao Kolipaka; Mario Szegedy; Yixin Xu (APPROX-RANDOM, 2012)

Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis. - Matthias Poloczek; Mario Szegedy (FOCS, 2012)

Streaming and Communication Complexity of Clique Approximation. - Magnús M. Halldórsson; Xiaoming Sun 001; Mario Szegedy; Chengu Wang (ICALP (1), 2012)

Mechanism design: from partial to probabilistic verification. - Ioannis Caragiannis; Edith Elkind; Mario Szegedy; Lan Yu (EC, 2012)

Digital Signatures with Minimal Overhead. - Eike Kiltz; Krzysztof Pietrzak; Mario Szegedy (IACR Cryptol. ePrint Arch., 2012)

Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions. - Eike Kiltz; Krzysztof Pietrzak; Mario Szegedy (CRYPTO (1), 2013)

The Lovász Local Lemma - A Survey. - Mario Szegedy (CSR, 2013)

The Garden Hose Complexity for the Equality Function. - Well Y. Chiu; Mario Szegedy; Chengu Wang; Yixin Xu (AAIM, 2014)

Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law. - Dorit Aharonov; Aram W. Harrow; Zeph Landau; Daniel Nagaj; Mario Szegedy; Umesh V. Vazirani (FOCS, 2014)

An $O(n^{0.4732})$ upper bound on the complexity of the GKS communication game. - Mario Szegedy (CoRR, 2015)

Impossibility Theorems and the Universal Algebraic Toolkit. - Mario Szegedy; Yixin Xu (CoRR, 2015)

Streaming Algorithms for Independent Sets in Sparse Hypergraphs. - Bjarni V. Halldórsson; Magnús M. Halldórsson; Elena Losievskaja; Mario Szegedy (Algorithmica, 2016)

A Graph-based Model for GPU Caching Problems. - Lingda Li; Ari B. Hayes; Stephen A. Hackler; Eddy Z. Zhang; Mario Szegedy; Shuaiwen Leon Song (CoRR, 2016)

Quantum Analogues of Markov Chains. - Ashwin Nayak 001; Peter C. Richter; Mario Szegedy (Encyclopedia of Algorithms, 2016)

The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry). - Jan Dean Catarata; Scott Corbett; Harry Stern; Mario Szegedy; Tomás Vyskocil; Zheng Zhang (ALENEX, 2017)

A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing. - Lingda Li; Robel Geda; Ari B. Hayes; Yan-Hao Chen; Pranav Chaudhari; Eddy Z. Zhang; Mario Szegedy (Proc. ACM Meas. Anal. Comput. Syst., 2017)

Explicit lower bounds on strong simulation of quantum circuits in terms of $T$-gate count. - Cupjin Huang; Michael Newman; Mario Szegedy (CoRR, 2019)

Explicit Lower Bounds on Strong Quantum Simulation. - Cupjin Huang; Michael Newman; Mario Szegedy (IEEE Trans. Inf. Theory, 2020)

On Rearrangement of Items Stored in Stacks. - Mario Szegedy; Jingjin Yu (WAFR, 2021)

Efficient parallelization of tensor network contraction for simulating quantum computation. - Cupjin Huang; Fang Zhang; Michael Newman; Xiaotong Ni; Dawei Ding 002; Junjie Cai; Xun Gao; Tenghui Wang; Feng Wu; Gengyan Zhang; Hsiang-Sheng Ku; Zhengxiong Tian; et al. (Nat. Comput. Sci., 2021)

Query Complexity - Mario Szegedy; Ilan Newman; Troy Lee (WorldScientific, 2022)

Rubik Tables, Stack Rearrangement, and Multi-Robot Path Planning. - Teng Guo; Si Wei Feng; Mario Szegedy; Jingjin Yu (Allerton, 2022)

Budgeted Steiner Networks: Three Terminals with Equal Path Weights. - Jingjin Yu; Mario Szegedy (CCCG, 2022)

Repeated Averages on Graphs. - Ramis Movassagh; Mario Szegedy; Guanyang Wang (CoRR, 2022)

Quantum Locally Testable Code with Exotic Parameters. - Andrew W. Cross; Zhiyang He; Anand Natarajan 001; Mario Szegedy; Guanyu Zhu (CoRR, 2022)

An Initial Study of Budgeted Steiner Networks. - Mario Szegedy; Jingjin Yu (Comput. Geom. Topol., 2023)

Rubik Tables and object rearrangement. - Mario Szegedy; Jingjin Yu (Int. J. Robotics Res., 2023)

Generating k EPR-pairs from an n-party resource state. - Sergey Bravyi 001; Yash Sharma; Mario Szegedy; Ronald de Wolf (Quantum, 2024)

Quantum Locally Testable Code with Constant Soundness. - Andrew W. Cross; Zhiyang He; Anand Natarajan 001; Mario Szegedy; Guanyu Zhu (Quantum, 2024)

Non-linear Quantum Monte Carlo. - Jose H. Blanchet; Yassine Hamoudi; Mario Szegedy; Guanyang Wang (CoRR, 2025)