Mario Szegedy

Kashyap Babu Rao Kolipaka, Mario Szegedy, Yixin Xu: A Sharper Local Lemma with Improved Applications. APPROX-RANDOM 2012: 603-614

Matthias Poloczek, Mario Szegedy: Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis. FOCS 2012: 708-717

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

Ioannis Caragiannis, Edith Elkind, Mario Szegedy, Lan Yu: Mechanism design: from partial to probabilistic verification. ACM Conference on Electronic Commerce 2012: 266-283

Eike Kiltz, Krzysztof Pietrzak, Mario Szegedy: Digital Signatures with Minimal Overhead. IACR Cryptology ePrint Archive 2012: 658 (2012)

Ákos Seress, Mario Szegedy: Combinatorics, Groups, Algorithms, and Complexity: Conference in honor of Laci Babai's 60th birthday. Discrete Mathematics & Theoretical Computer Science 13(4): 1-4 (2011)

Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy: Quantum Query Complexity of State Conversion. FOCS 2011: 344-353

Kashyap Babu Rao Kolipaka, Mario Szegedy: Moser and tardos meet Lovász. STOC 2011: 235-244

William Steiger, Mario Szegedy, Jihui Zhao: Six-way equipartitioning by three lines in the plane. CCCG 2010: 277-280

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

Miklos Santha, Mario Szegedy: Quantum and Classical Query Complexities of Local Search Are Polynomially Related. Algorithmica 55(3): 557-575 (2009)

Padmini Mukkamala, Mario Szegedy: Geometric representation of cubic graphs with four directions. Comput. Geom. 42(9): 842-851 (2009)

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

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

Gábor Kun, Mario Szegedy: A new line of attack on the dichotomy conjecture. STOC 2009: 725-734

Gábor Kun, Mario Szegedy: A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE. Electronic Colloquium on Computational Complexity (ECCC) 16: 59 (2009)

Kooshiar Azimian, Mario Szegedy: Parallel Repetition of the Odd Cycle Game. LATIN 2008: 676-686

Xiaomin Chen, János Pach, Mario Szegedy, Gábor Tardos: Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. SODA 2008: 94-101

Peter Richter, Mario Szegedy: Quantization of Markov Chains. Encyclopedia of Algorithms 2008

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

Mario Szegedy, Mikkel Thorup: On the Variance of Subset Sum Estimation. ESA 2007: 75-86

Rajat Mittal, Mario Szegedy: Product Rules in Semidefinite Programming. FCT 2007: 435-445

Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien: Languages with Bounded Multiparty Communication Complexity. STACS 2007: 500-511

Mario Szegedy, Mikkel Thorup: On the variance of subset sum estimation. CoRR abs/cs/0702029 (2007)

Sophie Laplante, Troy Lee, Mario Szegedy: The Quantum Adversary Method and Classical Formula Size Lower Bounds. Computational Complexity 15(2): 163-196 (2006)

Robert Spalek, Mario Szegedy: All Quantum Adversary Methods are Equivalent. Theory of Computing 2(1): 1-18 (2006)

Su Chen, Tomasz Imielinski, Karin Johnsgard, Donald Smith, Mario Szegedy: A Dichotomy Theorem for Typed Constraint Satisfaction Problems. SAT 2006: 226-239

Mario Szegedy: The DLT priority sampling is essentially optimal. STOC 2006: 150-158

Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien: Languages with Bounded Multiparty Communication Complexity. Electronic Colloquium on Computational Complexity (ECCC) 13(117) (2006)

Sophie Laplante, Troy Lee, Mario Szegedy: The Quantum Adversary Method and Classical Formula Size Lower Bounds. IEEE Conference on Computational Complexity 2005: 76-90

Xiaomin Chen, Mario Szegedy, Lei Wang: Optimally Balanced Forward Degree Sequence. COCOON 2005: 680-689

Robert Spalek, Mario Szegedy: All Quantum Adversary Methods Are Equivalent. ICALP 2005: 1299-1311

Frédéric Magniez, Miklos Santha, Mario Szegedy: Quantum algorithms for the triangle problem. SODA 2005: 1109-1117

Mario Szegedy: Near optimality of the priority sampling procedure. Electronic Colloquium on Computational Complexity (ECCC)(001) (2005)

József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy: Long Monotone Paths in Line Arrangements. Discrete & Computational Geometry 32(2): 167-176 (2004)

Mario Szegedy, Xiaomin Chen: Computing Boolean functions from multiple faulty copies of input bits. Theor. Comput. Sci. 321(1): 149-170 (2004)

Mario Szegedy: Quantum Speed-Up of Markov Chain Based Algorithms. FOCS 2004: 32-41

Miklos Santha, Mario Szegedy: Quantum and classical query complexities of local search are polynomially related. STOC 2004: 494-501

Howard Barnum, Michael E. Saks, Mario Szegedy: Quantum query complexity and semi-definite programming. IEEE Conference on Computational Complexity 2003: 179-193

József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy: Long monotone paths in line arrangements. Symposium on Computational Geometry 2003: 124-128

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

Mario Szegedy, Xiaomin Chen: Computing Boolean Functions from Multiple Faulty Copies of Input Bits. LATIN 2002: 539-553

Noga Alon, Eldar Fischer, Mario Szegedy: Parent-Identifying Codes. J. Comb. Theory, Ser. A 95(2): 349-359 (2001)

Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy: Efficient Testing of Large Graphs. Combinatorica 20(4): 451-476 (2000)

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

Noga Alon, Mario Szegedy: Large Sets of Nearly Orthogonal Vectors. Graphs and Combinatorics 15(1): 1-4 (1999)

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

Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy: Regular Languages Are Testable with a Constant Number of Queries. FOCS 1999: 645-655

Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy: Efficient Testing of Large Graphs. FOCS 1999: 656-666

Mario Szegedy: Many-Valued Logics and Holographic Proofs. ICALP 1999: 676-686

Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy: Tracking Join and Self-Join Sizes in Limited Storage. PODS 1999: 10-20

Haim Kaplan, Mario Szegedy: On-line Complexity of Monotone Set Systems. SODA 1999: 507-516

David S. Johnson, Mario Szegedy: What are the Least Tractable Instances of max Tndependent Set? SODA 1999: 927-928

Haim Kaplan, Martin Strauss, Mario Szegedy: Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data. SODA 1999: 935-936

Mario Szegedy: A Slique Size Bounding Technique with Application to Non-Linear Codes. SODA 1999: 971-972

Mario Szegedy: In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved? STACS 1999: 356-361

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof Verification and the Hardness of Approximation Problems. J. ACM 45(3): 501-555 (1998)

Mario Szegedy: Algorithms to Tile the Infinite Grid with Finite Clusters. FOCS 1998: 137-147

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof verification and the hardness of approximation problems. Electronic Colloquium on Computational Complexity (ECCC) 5(8) (1998)

László Lovász, János Pach, Mario Szegedy: On Conway's Thrackle Conjecture. Discrete & Computational Geometry 18(4): 369-376 (1997)

János Pach, Farhad Shahrokhi, Mario Szegedy: Applications of the Crossing Number. Algorithmica 16(1): 111-117 (1996)

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

Noga Alon, Yossi Matias, Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. STOC 1996: 20-29

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

Anna Gál, Mario Szegedy: Fault Tolerant Circuits and Probabilistically Checkable Proofs. Structure in Complexity Theory Conference 1995: 65-73

László Lovász, János Pach, Mario Szegedy: On Conway's Thrackle Conjecture. Symposium on Computational Geometry 1995: 147-151

Noam Nisan, Mario Szegedy: On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4: 301-313 (1994)

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

János Pach, Farhad Shahrokhi, Mario Szegedy: Applications of the Crossing Number. Symposium on Computational Geometry 1994: 198-202

Mario Szegedy: A note on the Theta number of Lovász and the generalized Delsarte bound. FOCS 1994: 36-39

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

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

Mario Szegedy, Sundar Vishwanathan: Locality based graph coloring. STOC 1993: 201-207

Péter Hajnal, Mario Szegedy: On packing bipartite graphs. Combinatorica 12(3): 295-301 (1992)

László Babai, Mario Szegedy: Local Expansion of Ssymmetrical Graphs. Combinatorics, Probability & Computing 1: 1-11 (1992)

Lance Fortnow, Mario Szegedy: On the Power of Two-Local Random Reductions. Inf. Process. Lett. 44(6): 303-306 (1992)

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

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof Verification and Hardness of Approximation Problems. FOCS 1992: 14-23

Magnús M. Halldórsson, Mario Szegedy: Lower Bounds for On-Line Graph Coloring. SODA 1992: 211-216

Noam Nisan, Mario Szegedy: On the Degree of Boolean Functions as Real Polynomials. STOC 1992: 462-467

Janos Simon, Mario Szegedy: On the Complexity of RAM with Various Operation Sets. STOC 1992: 624-631

Lance Fortnow, Mario Szegedy: On the Power of Two-Local Random Reductions. ASIACRYPT 1991: 346-351

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

László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy: Checking Computations in Polylogarithmic Time. STOC 1991: 21-31

Mario Szegedy: Functions with Bounded Symmetric Communication Complexity and Circuits with \mathop mod m Gates. STOC 1990: 278-286

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

David Rubinstein, Jeffrey Shallit, Mario Szegedy: A Subset Coloring Algorithm and Its Applications to Computer Graphics. Commun. ACM 31(10): 1228-1232 (1988)

András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán: Threshold circuits of bounded depth. FOCS 1987: 99-110

Mario Szegedy: The solution of Graham's greatest common divisor problem. Combinatorica 6(1): 67-71 (1986)

Gustav Burosch, Waleri Wassiljewitsch Gorlow, Roger Labahn, Mario Szegedy: The Telephone Problem for Connected Graphs. Elektronische Informationsverarbeitung und Kybernetik 20(10/11): 557-573 (1984)