| 2025 | WSC | Connecting Quantum Computing with Classical Stochastic Simulation. | Jose H. Blanchet, Mark S. Squillante, Mario Szegedy, Guanyang Wang |
| 2021 | WAFR | On Rearrangement of Items Stored in Stacks. | Mario Szegedy, Jingjin Yu |
| 2017 | ALENEX | The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry). | Jan Dean Catarata, Scott Corbett, Harry Stern, Mario Szegedy, Toms Vyskocil, Zheng Zhang |
| 2017 | SIGMETRICS | 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 |
| 2014 | AAIM | The Garden Hose Complexity for the Equality Function. | Well Y. Chiu, Mario Szegedy, Chengu Wang, Yixin Xu |
| 2014 | FOCS | 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 |
| 2013 | CRYPTO | Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions. | Eike Kiltz, Krzysztof Pietrzak, Mario Szegedy |
| 2013 | CSR | The Lovsz Local Lemma - A Survey. | Mario Szegedy |
| 2012 | FOCS | Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis. | Matthias Poloczek, Mario Szegedy |
| 2012 | ICALP | Streaming and Communication Complexity of Clique Approximation. | Magns M. Halldrsson, Xiaoming Sun, Mario Szegedy, Chengu Wang |
| 2011 | FOCS | Quantum Query Complexity of State Conversion. | Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy |
| 2011 | STOC | Moser and tardos meet Lovsz. | Kashyap Babu Rao Kolipaka, Mario Szegedy |
| 2010 | ICALP | Streaming Algorithms for Independent Sets. | Bjarni V. Halldrsson, Magns M. Halldrsson, Elena Losievskaja, Mario Szegedy |
| 2009 | ICALP | Amortized Communication Complexity of Distributions. | Jrmie Roland, Mario Szegedy |
| 2009 | STOC | A new line of attack on the dichotomy conjecture. | Gbor Kun, Mario Szegedy |
| 2008 | LATIN | Parallel Repetition of the Odd Cycle Game. | Kooshiar Azimian, Mario Szegedy |
| 2008 | SODA | Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. | Xiaomin Chen, Jnos Pach, Mario Szegedy, Gbor Tardos |
| 2007 | ESA | On the Variance of Subset Sum Estimation. | Mario Szegedy, Mikkel Thorup |
| 2007 | FCT | Product Rules in Semidefinite Programming. | Rajat Mittal, Mario Szegedy |
| 2007 | STACS | Languages with Bounded Multiparty Communication Complexity. | Arkadev Chattopadhyay, Andreas Krebs, Michal Kouck, Mario Szegedy, Pascal Tesson, Denis Thrien |
| 2006 | STOC | The DLT priority sampling is essentially optimal. | Mario Szegedy |
| 2006 | SAT | A Dichotomy Theorem for Typed Constraint Satisfaction Problems. | Su Chen, Tomasz Imielinski, Karin Johnsgard, Donald Smith, Mario Szegedy |
| 2005 | COCOON | Optimally Balanced Forward Degree Sequence. | Xiaomin Chen, Mario Szegedy, Lei Wang |
| 2005 | ICALP | All Quantum Adversary Methods Are Equivalent. | Robert Spalek, Mario Szegedy |
| 2005 | SODA | Quantum algorithms for the triangle problem. | Frdric Magniez, Miklos Santha, Mario Szegedy |
| 2004 | FOCS | Quantum Speed-Up of Markov Chain Based Algorithms. | Mario Szegedy |
| 2004 | STOC | Quantum and classical query complexities of local search are polynomially related. | Miklos Santha, Mario Szegedy |
| 2002 | LATIN | Computing Boolean Functions from Multiple Faulty Copies of Input Bits. | Mario Szegedy, Xiaomin Chen |
| 1999 | FOCS | Efficient Testing of Large Graphs. | Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy |
| 1999 | FOCS | Regular Languages Are Testable with a Constant Number of Queries. | Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy |
| 1999 | ICALP | Many-Valued Logics and Holographic Proofs. | Mario Szegedy |
| 1999 | PODS | Tracking Join and Self-Join Sizes in Limited Storage. | Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy |
| 1999 | SODA | What are the Least Tractable Instances of max Independent Set? | David S. Johnson, Mario Szegedy |
| 1999 | SODA | On-line Complexity of Monotone Set Systems. | Haim Kaplan, Mario Szegedy |
| 1999 | SODA | Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data. | Haim Kaplan, Martin Strauss, Mario Szegedy |
| 1999 | SODA | A Slique Size Bounding Technique with Application to Non-Linear Codes. | Mario Szegedy |
| 1999 | STACS | In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved? | Mario Szegedy |
| 1998 | FOCS | Algorithms to Tile the Infinite Grid with Finite Clusters. | Mario Szegedy |
| 1996 | STOC | The Space Complexity of Approximating the Frequency Moments. | Noga Alon, Yossi Matias, Mario Szegedy |
| 1996 | STOC | Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). | Ilan Newman, Mario Szegedy |
| 1994 | FOCS | A note on the Theta number of Lovsz and the generalized Delsarte bound | Mario Szegedy |
| 1993 | STOC | Locality based graph coloring. | Mario Szegedy, Sundar Vishwanathan |
| 1992 | FOCS | Proof Verification and Hardness of Approximation Problems | Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy |
| 1992 | SODA | Lower Bounds for On-Line Graph Coloring. | Magns M. Halldrsson, Mario Szegedy |
| 1992 | STOC | On the Degree of Boolean Functions as Real Polynomials | Noam Nisan, Mario Szegedy |
| 1992 | STOC | On the Complexity of RAM with Various Operation Sets | Janos Simon, Mario Szegedy |
| 1991 | ASIACRYPT | On the Power of Two-Local Random Reductions. | Lance Fortnow, Mario Szegedy |
| 1991 | FOCS | Approximating Clique is Almost NP-Complete (Preliminary Version) | Uriel Feige, Shafi Goldwasser, Lszl Lovsz, Shmuel Safra, Mario Szegedy |
| 1991 | STOC | Checking Computations in Polylogarithmic Time | Lszl Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy |
| 1990 | STOC | Functions with Bounded Symmetric Communication Complexity and Circuits with \mathop mod m Gates | Mario Szegedy |
| 1989 | STOC | Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract) | Lszl Babai, Noam Nisan, Mario Szegedy |
| 1987 | FOCS | Threshold circuits of bounded depth | Andrs Hajnal, Wolfgang Maass, Pavel Pudlk, Mario Szegedy, Gyrgy Turn |