Mario Szegedy

127 papers A* 34A 8B 3C 2Misc 2Journal 59Unranked 15
YearRankTypeTitle / Venue / Authors
2026 J jnl
Debate is efficient with your time.
CoRR
Jonah Brown-Cohen, Geoffrey Irving, Simon C. Marshall, Ilan Newman, Georgios Piliouras, Mario Szegedy
2025 J jnl
Connecting Quantum Computing with Classical Stochastic Simulation.
CoRR
Jose H. Blanchet, Mark S. Squillante, Mario Szegedy, Guanyang Wang
2025 J jnl
Non-linear Quantum Monte Carlo.
CoRR
Jose H. Blanchet, Yassine Hamoudi, Mario Szegedy, Guanyang Wang
2025 J jnl
On the Brittleness of LLMs: A Journey around Set Membership.
CoRR
Lea Hergert, Gábor Berend, Mario Szegedy, György Turán, Márk Jelasity
2024 J jnl
Generating k EPR-pairs from an n-party resource state.
Quantum
Sergey Bravyi, Yash Sharma, Mario Szegedy, Ronald de Wolf
2024 J jnl
Quantum Locally Testable Code with Constant Soundness.
Quantum
Andrew W. Cross, Zhiyang He, Anand Natarajan, Mario Szegedy, Guanyu Zhu
2023 J jnl
An Initial Study of Budgeted Steiner Networks.
Comput. Geom. Topol.
Mario Szegedy, Jingjin Yu
2023 J jnl
Rubik Tables and object rearrangement.
Int. J. Robotics Res.
Mario Szegedy, Jingjin Yu
2022 — conf
Budgeted Steiner Networks: Three Terminals with Equal Path Weights.
CCCG
Jingjin Yu, Mario Szegedy
2022 J jnl
Budgeted Steiner Networks: Three Terminals with Equal Path Weights.
CoRR
Mario Szegedy, Jingjin Yu
2022 J jnl
Quantum Locally Testable Code with Exotic Parameters.
CoRR
Andrew W. Cross, Zhiyang He, Anand Natarajan, Mario Szegedy, Guanyu Zhu
2022 — book
Query Complexity
Mario Szegedy, Ilan Newman, Troy Lee
2022 J jnl
Repeated Averages on Graphs.
CoRR
Ramis Movassagh, Mario Szegedy, Guanyang Wang
2022 — conf
Rubik Tables, Stack Rearrangement, and Multi-Robot Path Planning.
Allerton
Teng Guo, Si Wei Feng, Mario Szegedy, Jingjin Yu
2021 J jnl
Efficient parallelization of tensor network contraction for simulating quantum computation.
Nat. Comput. Sci.
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
2021 C conf
On Rearrangement of Items Stored in Stacks.
WAFR
Mario Szegedy, Jingjin Yu
2020 J jnl
Explicit Lower Bounds on Strong Quantum Simulation.
IEEE Trans. Inf. Theory
Cupjin Huang, Michael Newman, Mario Szegedy
2020 J jnl
On Rearrangement of Items Stored in Stacks.
CoRR
Mario Szegedy, Jingjin Yu
2019 J jnl
Explicit lower bounds on strong simulation of quantum circuits in terms of $T$-gate count.
CoRR
Cupjin Huang, Michael Newman, Mario Szegedy
2018 J jnl
Explicit lower bounds on strong quantum simulation.
CoRR
Cupjin Huang, Michael Newman, Mario Szegedy
2017 — conf
A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing.
SIGMETRICS (Abstracts)
Lingda Li, Robel Geda, Ari B. Hayes, Yan-Hao Chen, Pranav Chaudhari, Eddy Z. Zhang, Mario Szegedy
2017 J jnl
A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing.
Proc. ACM Meas. Anal. Comput. Syst.
Lingda Li, Robel Geda, Ari B. Hayes, Yan-Hao Chen, Pranav Chaudhari, Eddy Z. Zhang, Mario Szegedy
2017 A conf
The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry).
ALENEX
Jan Dean Catarata, Scott Corbett, Harry Stern, Mario Szegedy, Tomás Vyskocil, Zheng Zhang
2016 J jnl
A Graph-based Model for GPU Caching Problems.
CoRR
Lingda Li, Ari B. Hayes, Stephen A. Hackler, Eddy Z. Zhang, Mario Szegedy, Shuaiwen Leon Song
2016 J jnl
A new line of attack on the dichotomy conjecture.
Eur. J. Comb.
Gábor Kun, Mario Szegedy
2016 — ch.
Quantum Analogues of Markov Chains.
Encyclopedia of Algorithms
Ashwin Nayak, Peter C. Richter, Mario Szegedy
2016 J jnl
Streaming Algorithms for Independent Sets in Sparse Hypergraphs.
Algorithmica
Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, Mario Szegedy
2015 J jnl
An $O(n^{0.4732})$ upper bound on the complexity of the GKS communication game.
CoRR
Mario Szegedy
2015 J jnl
Impossibility Theorems and the Universal Algebraic Toolkit.
CoRR
Mario Szegedy, Yixin Xu
2014 A* conf
Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law.
FOCS
Dorit Aharonov, Aram W. Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, Umesh V. Vazirani
2014 C conf
The Garden Hose Complexity for the Equality Function.
AAIM
Well Y. Chiu, Mario Szegedy, Chengu Wang, Yixin Xu
2013 — conf
Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions.
CRYPTO (1)
Eike Kiltz, Krzysztof Pietrzak, Mario Szegedy
2013 J jnl
The Garden Hose Complexity for the Equality Function.
CoRR
Well Y. Chiu, Mario Szegedy, Chengu Wang, Yixin Xu
2013 Misc conf
The Lovász Local Lemma - A Survey.
CSR
Mario Szegedy
2012 — conf
A Sharper Local Lemma with Improved Applications.
APPROX-RANDOM
Kashyap Babu Rao Kolipaka, Mario Szegedy, Yixin Xu
2012 J jnl
Digital Signatures with Minimal Overhead.
IACR Cryptol. ePrint Arch.
Eike Kiltz, Krzysztof Pietrzak, Mario Szegedy
2012 A* conf
Mechanism design: from partial to probabilistic verification.
EC
Ioannis Caragiannis, Edith Elkind, Mario Szegedy, Lan Yu
2012 A* conf
Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis.
FOCS
Matthias Poloczek, Mario Szegedy
2012 — conf
Streaming and Communication Complexity of Clique Approximation.
ICALP (1)
Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy, Chengu Wang
2011 J jnl
Combinatorics, Groups, Algorithms, and Complexity: Conference in honor of Laci Babai's 60th birthday.
Discret. Math. Theor. Comput. Sci.
Ákos Seress, Mario Szegedy
2011 A* conf
Moser and tardos meet Lovász.
STOC
Kashyap Babu Rao Kolipaka, Mario Szegedy
2011 A* conf
Quantum Query Complexity of State Conversion.
FOCS
Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy
2010 — conf
Six-way equipartitioning by three lines in the plane.
CCCG
William Steiger, Mario Szegedy, Jihui Zhao
2010 — conf
Streaming Algorithms for Independent Sets.
ICALP (1)
Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, Mario Szegedy
2009 J jnl
A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE.
Electron. Colloquium Comput. Complex.
Gábor Kun, Mario Szegedy
2009 A* conf
A new line of attack on the dichotomy conjecture.
STOC
Gábor Kun, Mario Szegedy
2009 — conf
Amortized Communication Complexity of Distributions.
ICALP (1)
Jérémie Roland, Mario Szegedy
2009 J jnl
Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles.
Random Struct. Algorithms
Xiaomin Chen, János Pach, Mario Szegedy, Gábor Tardos
2009 J jnl
Geometric representation of cubic graphs with four directions.
Comput. Geom.
Padmini Mukkamala, Mario Szegedy
2009 J jnl
Quantum and Classical Query Complexities of Local Search Are Polynomially Related.
Algorithmica
Miklos Santha, Mario Szegedy
2008 A* conf
Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles.
SODA
Xiaomin Chen, János Pach, Mario Szegedy, Gábor Tardos
2008 B conf
Parallel Repetition of the Odd Cycle Game.
LATIN
Kooshiar Azimian, Mario Szegedy
2008 — ch.
Quantization of Markov Chains.
Encyclopedia of Algorithms
Peter C. Richter, Mario Szegedy
2007 — ch.
Hardness of Approximation.
Handbook of Approximation Algorithms and Metaheuristics
Mario Szegedy
2007 A conf
Languages with Bounded Multiparty Communication Complexity.
STACS
Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien
2007 A conf
On the Variance of Subset Sum Estimation.
ESA
Mario Szegedy, Mikkel Thorup
2007 J jnl
On the variance of subset sum estimation
CoRR
Mario Szegedy, Mikkel Thorup
2007 B conf
Product Rules in Semidefinite Programming.
FCT
Rajat Mittal, Mario Szegedy
2007 J jnl
Quantum Algorithms for the Triangle Problem.
SIAM J. Comput.
Frédéric Magniez, Miklos Santha, Mario Szegedy
2006 A conf
A Dichotomy Theorem for Typed Constraint Satisfaction Problems.
SAT
Su Chen, Tomasz Imielinski, Karin Johnsgard, Donald Smith, Mario Szegedy
2006 J jnl
All Quantum Adversary Methods are Equivalent.
Theory Comput.
Robert Spalek, Mario Szegedy
2006 J jnl
Languages with Bounded Multiparty Communication Complexity.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien
2006 A* conf
The DLT priority sampling is essentially optimal.
STOC
Mario Szegedy
2006 J jnl
The Quantum Adversary Method and Classical Formula Size Lower Bounds.
Comput. Complex.
Sophie Laplante, Troy Lee, Mario Szegedy
2005 A* conf
All Quantum Adversary Methods Are Equivalent.
ICALP
Robert Spalek, Mario Szegedy
2005 J jnl
Near optimality of the priority sampling procedure
Electron. Colloquium Comput. Complex.
Mario Szegedy
2005 Misc conf
Optimally Balanced Forward Degree Sequence.
COCOON
Xiaomin Chen, Mario Szegedy, Lei Wang
2005 A* conf
Quantum algorithms for the triangle problem.
SODA
Frédéric Magniez, Miklos Santha, Mario Szegedy
2005 A conf
The Quantum Adversary Method and Classical Formula Size Lower Bounds.
CCC
Sophie Laplante, Troy Lee, Mario Szegedy
2004 J jnl
Computing Boolean functions from multiple faulty copies of input bits.
Theor. Comput. Sci.
Mario Szegedy, Xiaomin Chen
2004 J jnl
Long Monotone Paths in Line Arrangements.
Discret. Comput. Geom.
József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy
2004 A* conf
Quantum Speed-Up of Markov Chain Based Algorithms.
FOCS
Mario Szegedy
2004 A* conf
Quantum and classical query complexities of local search are polynomially related.
STOC
Miklos Santha, Mario Szegedy
2003 — conf
Long monotone paths in line arrangements.
SCG
József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy
2003 A conf
Quantum query complexity and semi-definite programming.
CCC
Howard Barnum, Michael E. Saks, Mario Szegedy
2002 B conf
Computing Boolean Functions from Multiple Faulty Copies of Input Bits.
LATIN
Mario Szegedy, Xiaomin Chen
2002 J jnl
Tracking Join and Self-Join Sizes in Limited Storage.
J. Comput. Syst. Sci.
Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy
2001 J jnl
Parent-Identifying Codes.
J. Comb. Theory A
Noga Alon, Eldar Fischer, Mario Szegedy
2000 J jnl
Efficient Testing of Large Graphs.
Comb.
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
2000 J jnl
Regular Languages are Testable with a Constant Number of Queries.
SIAM J. Comput.
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
1999 A* conf
A Slique Size Bounding Technique with Application to Non-Linear Codes.
SODA
Mario Szegedy
1999 A* conf
Efficient Testing of Large Graphs.
FOCS
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
1999 A conf
In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved?
STACS
Mario Szegedy
1999 A* conf
Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data.
SODA
Haim Kaplan, Martin Strauss, Mario Szegedy
1999 J jnl
Large Sets of Nearly Orthogonal Vectors.
Graphs Comb.
Noga Alon, Mario Szegedy
1999 A* conf
Many-Valued Logics and Holographic Proofs.
ICALP
Mario Szegedy
1999 A* conf
On-line Complexity of Monotone Set Systems.
SODA
Haim Kaplan, Mario Szegedy
1999 A* conf
Regular Languages Are Testable with a Constant Number of Queries.
FOCS
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
1999 J jnl
The Space Complexity of Approximating the Frequency Moments.
J. Comput. Syst. Sci.
Noga Alon, Yossi Matias, Mario Szegedy
1999 A* conf
Tracking Join and Self-Join Sizes in Limited Storage.
PODS
Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy
1999 A* conf
What are the Least Tractable Instances of max Independent Set?
SODA
David S. Johnson, Mario Szegedy
1998 A* conf
Algorithms to Tile the Infinite Grid with Finite Clusters.
FOCS
Mario Szegedy
1998 J jnl
Proof Verification and the Hardness of Approximation Problems.
J. ACM
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
1998 J jnl
Proof verification and the hardness of approximation problems.
Electron. Colloquium Comput. Complex.
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
1997 J jnl
On Conway's Thrackle Conjecture.
Discret. Comput. Geom.
László Lovász, János Pach, Mario Szegedy
1996 J jnl
Applications of the Crossing Number.
Algorithmica
János Pach, Farhad Shahrokhi, Mario Szegedy
1996 J jnl
Interactive Proofs and the Hardness of Approximating Cliques.
J. ACM
Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy
1996 A* conf
Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract).
STOC
Ilan Newman, Mario Szegedy
1996 A* conf
The Space Complexity of Approximating the Frequency Moments.
STOC
Noga Alon, Yossi Matias, Mario Szegedy
1995 — conf
Fault Tolerant Circuits and Probabilistically Checkable Proofs.
SCT
Anna Gál, Mario Szegedy
1995 — conf
On Conway's Thrackle Conjecture.
SCG
László Lovász, János Pach, Mario Szegedy
1994 A* conf
A note on the Theta number of Lovász and the generalized Delsarte bound
FOCS
Mario Szegedy
1994 — conf
Applications of the Crossing Number.
SCG
János Pach, Farhad Shahrokhi, Mario Szegedy
1994 J jnl
Lower Bounds for On-Line Graph Coloring.
Theor. Comput. Sci.
Magnús M. Halldórsson, Mario Szegedy
1994 J jnl
On the Degree of Boolean Functions as Real Polynomials.
Comput. Complex.
Noam Nisan, Mario Szegedy
1993 J jnl
Functions with Bounded Symmetric Communication Complexity, Programs over Commutative Monoids, and ACC.
J. Comput. Syst. Sci.
Mario Szegedy
1993 A* conf
Locality based graph coloring.
STOC
Mario Szegedy, Sundar Vishwanathan
1993 J jnl
Threshold Circuits of Bounded Depth.
J. Comput. Syst. Sci.
András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán
1992 J jnl
Local Expansion of Ssymmetrical Graphs.
Comb. Probab. Comput.
László Babai, Mario Szegedy
1992 A* conf
Lower Bounds for On-Line Graph Coloring.
SODA
Magnús M. Halldórsson, Mario Szegedy
1992 J jnl
Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs.
J. Comput. Syst. Sci.
László Babai, Noam Nisan, Mario Szegedy
1992 J jnl
On packing bipartite graphs.
Comb.
Péter Hajnal, Mario Szegedy
1992 A* conf
On the Complexity of RAM with Various Operation Sets
STOC
Janos Simon, Mario Szegedy
1992 A* conf
On the Degree of Boolean Functions as Real Polynomials
STOC
Noam Nisan, Mario Szegedy
1992 J jnl
On the Power of Two-Local Random Reductions.
Inf. Process. Lett.
Lance Fortnow, Mario Szegedy
1992 A* conf
Proof Verification and Hardness of Approximation Problems
FOCS
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
1991 A* conf
Approximating Clique is Almost NP-Complete (Preliminary Version)
FOCS
Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy
1991 A* conf
Checking Computations in Polylogarithmic Time
STOC
László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy
1991 — conf
Lower Bounds for On-line Graph Coloring.
On-Line Algorithms
Magnús M. Halldórsson, Mario Szegedy
1991 A conf
On the Power of Two-Local Random Reductions.
ASIACRYPT
Lance Fortnow, Mario Szegedy
1990 — conf
A New Lower Bound Theorem for Read-Only-Once Branching Programs and its Applications.
Advances In Computational Complexity Theory
Janos Simon, Mario Szegedy
1990 A* conf
Functions with Bounded Symmetric Communication Complexity and Circuits with \mathop mod m Gates
STOC
Mario Szegedy
1989 A* conf
Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract)
STOC
László Babai, Noam Nisan, Mario Szegedy
1988 J jnl
A Subset Coloring Algorithm and Its Applications to Computer Graphics.
Commun. ACM
David Rubinstein, Jeffrey O. Shallit, Mario Szegedy
1987 A* conf
Threshold circuits of bounded depth
FOCS
András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán
1986 J jnl
The solution of Graham's greatest common divisor problem.
Comb.
Mario Szegedy
1984 J jnl
The Telephone Problem for Connected Graphs.
J. Inf. Process. Cybern.
Gustav Burosch, Waleri Wassiljewitsch Gorlow, Roger Labahn, Mario Szegedy