Mario Szegedy

According to our database, Mario Szegedy authored at least 92 papers between 1984 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

Rubik Tables and object rearrangement.

Mario Szegedy, Jingjin Yu

Int. J. Robotics Res., May, 2023

An Initial Study of Budgeted Steiner Networks.

Mario Szegedy, Jingjin Yu

Comput. Geom. Topol., 2023

2022

Quantum Locally Testable Code with Exotic Parameters.

Andrew W. Cross, Zhiyang He, Anand Natarajan, Mario Szegedy, Guanyu Zhu

CoRR, 2022

Repeated Averages on Graphs.

Ramis Movassagh, Mario Szegedy, Guanyang Wang

CoRR, 2022

Budgeted Steiner Networks: Three Terminals with Equal Path Weights.

Jingjin Yu, Mario Szegedy

Proceedings of the 34th Canadian Conference on Computational Geometry, 2022

Rubik Tables, Stack Rearrangement, and Multi-Robot Path Planning.

Teng Guo, Si Wei Feng, Mario Szegedy, Jingjin Yu

Proceedings of the 58th Annual Allerton Conference on Communication, 2022

Query Complexity

Mario Szegedy, Ilan Newman, Troy Lee

WorldScientific, ISBN: 9789813223226, 2022

2021

Efficient parallelization of tensor network contraction for simulating quantum computation.

Cupjin Huang, Fang Zhang, Michael Newman, Xiaotong Ni, Dawei Ding, Junjie Cai, Xun Gao, Tenghui Wang, Feng Wu, Gengyan Zhang, Hsiang-Sheng Ku, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, Hui-Hai Zhao, Chunqing Deng, Jianxin Chen

Nat. Comput. Sci., 2021

On Rearrangement of Items Stored in Stacks.

Mario Szegedy, Jingjin Yu

Proceedings of the Algorithmic Foundations of Robotics XIV, 2021

2020

Explicit Lower Bounds on Strong Quantum Simulation.

Cupjin Huang, Michael Newman, Mario Szegedy

IEEE Trans. Inf. Theory, 2020

2019

Explicit lower bounds on strong simulation of quantum circuits in terms of $T$-gate count.

Cupjin Huang, Michael Newman, Mario Szegedy

CoRR, 2019

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

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

Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments, 2017

2016

Quantum Analogues of Markov Chains.

Ashwin Nayak, Peter C. Richter, Mario Szegedy

Encyclopedia of Algorithms, 2016

A new line of attack on the dichotomy conjecture.

Gábor Kun, Mario Szegedy

Eur. J. Comb., 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

Streaming Algorithms for Independent Sets in Sparse Hypergraphs.

Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, Mario Szegedy

Algorithmica, 2016

2015

Impossibility Theorems and the Universal Algebraic Toolkit.

Mario Szegedy, Yixin Xu

CoRR, 2015

An $O(n^{0.4732})$ upper bound on the complexity of the GKS communication game.

Mario Szegedy

CoRR, 2015

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

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

The Garden Hose Complexity for the Equality Function.

Well Y. Chiu, Mario Szegedy, Chengu Wang, Yixin Xu

Proceedings of the Algorithmic Aspects in Information and Management, 2014

2013

The Lovász Local Lemma - A Survey.

Mario Szegedy

Proceedings of the Computer Science - Theory and Applications, 2013

Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions.

Eike Kiltz, Krzysztof Pietrzak, Mario Szegedy

Proceedings of the Advances in Cryptology - CRYPTO 2013, 2013

2012

Digital Signatures with Minimal Overhead.

Eike Kiltz, Krzysztof Pietrzak, Mario Szegedy

IACR Cryptol. ePrint Arch., 2012

Mechanism design: from partial to probabilistic verification.

Ioannis Caragiannis, Edith Elkind, Mario Szegedy, Lan Yu

Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

Streaming and Communication Complexity of Clique Approximation.

Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy, Chengu Wang

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis.

Matthias Poloczek, Mario Szegedy

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

A Sharper Local Lemma with Improved Applications.

Kashyap Babu Rao Kolipaka, Mario Szegedy, Yixin Xu

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

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

Moser and tardos meet Lovász.

Kashyap Babu Rao Kolipaka, Mario Szegedy

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Quantum Query Complexity of State Conversion.

Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Streaming Algorithms for Independent Sets.

Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, Mario Szegedy

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Six-way equipartitioning by three lines in the plane.

William Steiger, Mario Szegedy, Jihui Zhao

Proceedings of the 22nd Annual Canadian Conference on Computational Geometry, 2010

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

Geometric representation of cubic graphs with four directions.

Padmini Mukkamala, Mario Szegedy

Comput. Geom., 2009

Quantum and Classical Query Complexities of Local Search Are Polynomially Related.

Miklos Santha, Mario Szegedy

Algorithmica, 2009

Amortized Communication Complexity of Distributions.

Jérémie Roland, Mario Szegedy

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

Quantization of Markov Chains.

Peter C. Richter, Mario Szegedy

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Parallel Repetition of the Odd Cycle Game.

Kooshiar Azimian, Mario Szegedy

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

2007

Hardness of Approximation.

Mario Szegedy

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

Quantum Algorithms for the Triangle Problem.

Frédéric Magniez, Miklos Santha, Mario Szegedy

SIAM J. Comput., 2007

Product Rules in Semidefinite Programming.

Rajat Mittal, Mario Szegedy

Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

On the Variance of Subset Sum Estimation.

Mario Szegedy, Mikkel Thorup

Proceedings of the Algorithms, 2007

2006

All Quantum Adversary Methods are Equivalent.

Robert Spalek, Mario Szegedy

Theory Comput., 2006

Languages with Bounded Multiparty Communication Complexity.

Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

Electron. Colloquium Comput. Complex., 2006

The Quantum Adversary Method and Classical Formula Size Lower Bounds.

Sophie Laplante, Troy Lee, Mario Szegedy

Comput. Complex., 2006

The DLT priority sampling is essentially optimal.

Mario Szegedy

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

A Dichotomy Theorem for Typed Constraint Satisfaction Problems.

Su Chen, Tomasz Imielinski, Karin Johnsgard, Donald Smith, Mario Szegedy

Proceedings of the Theory and Applications of Satisfiability Testing, 2006

2005

Near optimality of the priority sampling procedure

Mario Szegedy

Electron. Colloquium Comput. Complex., 2005

Optimally Balanced Forward Degree Sequence.

Xiaomin Chen, Mario Szegedy, Lei Wang

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004

Computing Boolean functions from multiple faulty copies of input bits.

Mario Szegedy, Xiaomin Chen

Theor. Comput. Sci., 2004

Long Monotone Paths in Line Arrangements.

József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy

Discret. Comput. Geom., 2004

Quantum Speed-Up of Markov Chain Based Algorithms.

Mario Szegedy

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

Quantum query complexity and semi-definite programming.

Howard Barnum, Michael E. Saks, Mario Szegedy

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Tracking Join and Self-Join Sizes in Limited Storage.

Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy

J. Comput. Syst. Sci., 2002

2001

Parent-Identifying Codes.

Noga Alon, Eldar Fischer, Mario Szegedy

J. Comb. Theory, Ser. A, 2001

2000

Regular Languages are Testable with a Constant Number of Queries.

Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy

SIAM J. Comput., 2000

Efficient Testing of Large Graphs.

Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy

Comb., 2000

1999

The Space Complexity of Approximating the Frequency Moments.

Noga Alon, Yossi Matias, Mario Szegedy

J. Comput. Syst. Sci., 1999

Large Sets of Nearly Orthogonal Vectors.

Noga Alon, Mario Szegedy

Graphs Comb., 1999

In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved?

Mario Szegedy

Proceedings of the STACS 99, 1999

A Slique Size Bounding Technique with Application to Non-Linear Codes.

Mario Szegedy

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data.

Haim Kaplan, Martin Strauss, Mario Szegedy

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

On-line Complexity of Monotone Set Systems.

Haim Kaplan, Mario Szegedy

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

What are the Least Tractable Instances of max Independent Set?

David S. Johnson, Mario Szegedy

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Many-Valued Logics and Holographic Proofs.

Mario Szegedy

Proceedings of the Automata, 1999

1998

Proof Verification and the Hardness of Approximation Problems.

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

J. ACM, 1998

Algorithms to Tile the Infinite Grid with Finite Clusters.

Mario Szegedy

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

On Conway's Thrackle Conjecture.

László Lovász, János Pach, Mario Szegedy

Discret. Comput. Geom., 1997

1996

Interactive Proofs and the Hardness of Approximating Cliques.

Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy

J. ACM, 1996

Applications of the Crossing Number.

János Pach, Farhad Shahrokhi, Mario Szegedy

Algorithmica, 1996

Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract).

Ilan Newman, Mario Szegedy

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995

Fault Tolerant Circuits and Probabilistically Checkable Proofs.

Anna Gál, Mario Szegedy

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

Lower Bounds for On-Line Graph Coloring.

Magnús M. Halldórsson, Mario Szegedy

Theor. Comput. Sci., 1994

On the Degree of Boolean Functions as Real Polynomials.

Noam Nisan, Mario Szegedy

Comput. Complex., 1994

A note on the Theta number of Lovász and the generalized Delsarte bound

Mario Szegedy

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

Functions with Bounded Symmetric Communication Complexity, Programs over Commutative Monoids, and ACC.

Mario Szegedy

J. Comput. Syst. Sci., 1993

Threshold Circuits of Bounded Depth.

András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán

J. Comput. Syst. Sci., 1993

Locality based graph coloring.

Mario Szegedy, Sundar Vishwanathan

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992

Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs.

László Babai, Noam Nisan, Mario Szegedy

J. Comput. Syst. Sci., 1992

On the Power of Two-Local Random Reductions.

Lance Fortnow, Mario Szegedy

Inf. Process. Lett., 1992

Local Expansion of Ssymmetrical Graphs.

László Babai, Mario Szegedy

Comb. Probab. Comput., 1992

On packing bipartite graphs.

Péter Hajnal, Mario Szegedy

Comb., 1992

On the Complexity of RAM with Various Operation Sets

Janos Simon, Mario Szegedy

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991

Checking Computations in Polylogarithmic Time

László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Approximating Clique is Almost NP-Complete (Preliminary Version)

Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

Functions with Bounded Symmetric Communication Complexity and Circuits with \mathop mod m Gates

Mario Szegedy

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

A New Lower Bound Theorem for Read-Only-Once Branching Programs and its Applications.

Janos Simon, Mario Szegedy

Proceedings of the Advances In Computational Complexity Theory, 1990

1989

Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract)

László Babai, Noam Nisan, Mario Szegedy

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988

A Subset Coloring Algorithm and Its Applications to Computer Graphics.

David Rubinstein, Jeffrey O. Shallit, Mario Szegedy

Commun. ACM, 1988

1986

The solution of Graham's greatest common divisor problem.

Mario Szegedy

Comb., 1986

1984

The Telephone Problem for Connected Graphs.

Gustav Burosch, Waleri Wassiljewitsch Gorlow, Roger Labahn, Mario Szegedy

J. Inf. Process. Cybern., 1984