Mario Szegedy

Publication Activity (10 Years)

Years Active: 1984-2023
Publications (10 Years): 19

Top Venues

CoRR

IEEE Trans. Inf. Theory

AAIM

Nat. Comput. Sci.

Publications

Mario Szegedy, Jingjin Yu
Rubik Tables and object rearrangement. Int. J. Robotics Res. 42 (6) (2023)
Mario Szegedy, Jingjin Yu
An Initial Study of Budgeted Steiner Networks. Comput. Geom. Topol. 2 (2) (2023)
Andrew Cross, Zhiyang He, Anand Natarajan, Mario Szegedy, Guanyu Zhu
Quantum Locally Testable Code with Exotic Parameters. CoRR (2022)
Jingjin Yu, Mario Szegedy
Budgeted Steiner Networks: Three Terminals with Equal Path Weights. CCCG (2022)
Ramis Movassagh, Mario Szegedy, Guanyang Wang
Repeated Averages on Graphs. CoRR (2022)
Teng Guo, Si Wei Feng, Mario Szegedy, Jingjin Yu
Rubik Tables, Stack Rearrangement, and Multi-Robot Path Planning. Allerton (2022)
Mario Szegedy, Jingjin Yu
Budgeted Steiner Networks: Three Terminals with Equal Path Weights. CoRR (2022)
Mario Szegedy, Jingjin Yu
On Rearrangement of Items Stored in Stacks. WAFR (2021)
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
Efficient parallelization of tensor network contraction for simulating quantum computation. Nat. Comput. Sci. 1 (9) (2021)
Cupjin Huang, Michael Newman, Mario Szegedy
Explicit Lower Bounds on Strong Quantum Simulation. IEEE Trans. Inf. Theory 66 (9) (2020)
Mario Szegedy, Jingjin Yu
On Rearrangement of Items Stored in Stacks. CoRR (2020)
Cupjin Huang, Michael Newman, Mario Szegedy
Explicit lower bounds on strong simulation of quantum circuits in terms of $T$-gate count. CoRR (2019)
Cupjin Huang, Michael Newman, Mario Szegedy
Explicit lower bounds on strong quantum simulation. CoRR (2018)
Jan Dean Catarata, Scott Corbett, Harry Stern, Mario Szegedy, Tomás Vyskocil, Zheng Zhang
The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry). ALENEX (2017)
Lingda Li, Robel Geda, Ari B. Hayes, Yan-Hao Chen, Pranav Chaudhari, Eddy Z. Zhang, Mario Szegedy
A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing. Proc. ACM Meas. Anal. Comput. Syst. 1 (1) (2017)
Lingda Li, Robel Geda, Ari B. Hayes, Yan-Hao Chen, Pranav Chaudhari, Eddy Z. Zhang, Mario Szegedy
A Simple Yet Effective Balanced Edge Partition Model for Parallel Computing. SIGMETRICS (Abstracts) (2017)
Gábor Kun, Mario Szegedy
A new line of attack on the dichotomy conjecture. Eur. J. Comb. 52 (2016)
Lingda Li, Ari B. Hayes, Stephen A. Hackler, Eddy Z. Zhang, Mario Szegedy, Shuaiwen Leon Song
A Graph-based Model for GPU Caching Problems. CoRR (2016)
Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, Mario Szegedy
Streaming Algorithms for Independent Sets in Sparse Hypergraphs. Algorithmica 76 (2) (2016)
Mario Szegedy
An $O(n^{0.4732})$ upper bound on the complexity of the GKS communication game. CoRR (2015)
Mario Szegedy, Yixin Xu
Impossibility Theorems and the Universal Algebraic Toolkit. CoRR (2015)
Well Y. Chiu, Mario Szegedy, Chengu Wang, Yixin Xu
The Garden Hose Complexity for the Equality Function. AAIM (2014)
Dorit Aharonov, Aram W. Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, Umesh V. Vazirani
Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law. FOCS (2014)
Mario Szegedy
The Lovász Local Lemma - A Survey. CSR (2013)
Eike Kiltz, Krzysztof Pietrzak, Mario Szegedy
Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions. CRYPTO (1) (2013)
Well Y. Chiu, Mario Szegedy, Chengu Wang, Yixin Xu
The Garden Hose Complexity for the Equality Function. CoRR (2013)
Matthias Poloczek, Mario Szegedy
Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis. FOCS (2012)
Ioannis Caragiannis, Edith Elkind, Mario Szegedy, Lan Yu
Mechanism design: from partial to probabilistic verification. EC (2012)
Kashyap Babu Rao Kolipaka, Mario Szegedy, Yixin Xu
A Sharper Local Lemma with Improved Applications. APPROX-RANDOM (2012)
Eike Kiltz, Krzysztof Pietrzak, Mario Szegedy
Digital Signatures with Minimal Overhead. IACR Cryptol. ePrint Arch. 2012 (2012)
Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy, Chengu Wang
Streaming and Communication Complexity of Clique Approximation. ICALP (1) (2012)
Ákos Seress, Mario Szegedy
Combinatorics, Groups, Algorithms, and Complexity: Conference in honor of Laci Babai's 60th birthday. Discret. Math. Theor. Comput. Sci. 13 (4) (2011)
Kashyap Babu Rao Kolipaka, Mario Szegedy
Moser and tardos meet Lovász. STOC (2011)
Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy
Quantum Query Complexity of State Conversion. FOCS (2011)
William Steiger, Mario Szegedy, Jihui Zhao
Six-way equipartitioning by three lines in the plane. CCCG (2010)
Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, Mario Szegedy
Streaming Algorithms for Independent Sets. ICALP (1) (2010)
Jérémie Roland, Mario Szegedy
Amortized Communication Complexity of Distributions. ICALP (1) (2009)
Miklos Santha, Mario Szegedy
Quantum and Classical Query Complexities of Local Search Are Polynomially Related. Algorithmica 55 (3) (2009)
Gábor Kun, Mario Szegedy
A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE. Electron. Colloquium Comput. Complex. 16 (2009)
Padmini Mukkamala, Mario Szegedy
Geometric representation of cubic graphs with four directions. Comput. Geom. 42 (9) (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) (2009)
Gábor Kun, Mario Szegedy
A new line of attack on the dichotomy conjecture. STOC (2009)
Kooshiar Azimian, Mario Szegedy
Parallel Repetition of the Odd Cycle Game. LATIN (2008)
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)
Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien
Languages with Bounded Multiparty Communication Complexity. STACS (2007)
Rajat Mittal, Mario Szegedy
Product Rules in Semidefinite Programming. FCT (2007)
Mario Szegedy, Mikkel Thorup
On the variance of subset sum estimation CoRR (2007)
Mario Szegedy, Mikkel Thorup
On the Variance of Subset Sum Estimation. ESA (2007)
Frédéric Magniez, Miklos Santha, Mario Szegedy
Quantum Algorithms for the Triangle Problem. SIAM J. Comput. 37 (2) (2007)
Sophie Laplante, Troy Lee, Mario Szegedy
The Quantum Adversary Method and Classical Formula Size Lower Bounds. Comput. Complex. 15 (2) (2006)
Mario Szegedy
The DLT priority sampling is essentially optimal. STOC (2006)
Su Chen, Tomasz Imielinski, Karin Johnsgard, Donald Smith, Mario Szegedy
A Dichotomy Theorem for Typed Constraint Satisfaction Problems. SAT (2006)
Robert Spalek, Mario Szegedy
All Quantum Adversary Methods are Equivalent. Theory Comput. 2 (1) (2006)
Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien
Languages with Bounded Multiparty Communication Complexity. Electron. Colloquium Comput. Complex. 13 (117) (2006)
Mario Szegedy
Near optimality of the priority sampling procedure Electron. Colloquium Comput. Complex. (001) (2005)
Robert Spalek, Mario Szegedy
All Quantum Adversary Methods Are Equivalent. ICALP (2005)
Xiaomin Chen, Mario Szegedy, Lei Wang
Optimally Balanced Forward Degree Sequence. COCOON (2005)
Sophie Laplante, Troy Lee, Mario Szegedy
The Quantum Adversary Method and Classical Formula Size Lower Bounds. Computational Complexity Conference (2005)
Frédéric Magniez, Miklos Santha, Mario Szegedy
Quantum algorithms for the triangle problem. SODA (2005)
Mario Szegedy, Xiaomin Chen
Computing Boolean functions from multiple faulty copies of input bits. Theor. Comput. Sci. 321 (1) (2004)
Miklos Santha, Mario Szegedy
Quantum and classical query complexities of local search are polynomially related. STOC (2004)
Mario Szegedy
Quantum Speed-Up of Markov Chain Based Algorithms. FOCS (2004)
József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy
Long Monotone Paths in Line Arrangements. Discret. Comput. Geom. 32 (2) (2004)
Howard Barnum, Michael E. Saks, Mario Szegedy
Quantum query complexity and semi-definite programming. Computational Complexity Conference (2003)
József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy
Long monotone paths in line arrangements. SCG (2003)
Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy
Tracking Join and Self-Join Sizes in Limited Storage. J. Comput. Syst. Sci. 64 (3) (2002)
Mario Szegedy, Xiaomin Chen
Computing Boolean Functions from Multiple Faulty Copies of Input Bits. LATIN (2002)
Noga Alon, Eldar Fischer, Mario Szegedy
Parent-Identifying Codes. J. Comb. Theory, Ser. A 95 (2) (2001)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
Regular Languages are Testable with a Constant Number of Queries. SIAM J. Comput. 30 (6) (2000)
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Efficient Testing of Large Graphs. Comb. 20 (4) (2000)
Haim Kaplan, Mario Szegedy
On-line Complexity of Monotone Set Systems. SODA (1999)
David S. Johnson, Mario Szegedy
What are the Least Tractable Instances of max Independent Set? SODA (1999)
Noga Alon, Yossi Matias, Mario Szegedy
The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci. 58 (1) (1999)
Noga Alon, Mario Szegedy
Large Sets of Nearly Orthogonal Vectors. Graphs Comb. 15 (1) (1999)
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Efficient Testing of Large Graphs. FOCS (1999)
Haim Kaplan, Martin Strauss, Mario Szegedy
Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data. SODA (1999)
Mario Szegedy
Many-Valued Logics and Holographic Proofs. ICALP (1999)
Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy
Tracking Join and Self-Join Sizes in Limited Storage. PODS (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
Regular Languages Are Testable with a Constant Number of Queries. FOCS (1999)
Mario Szegedy
In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved? STACS (1999)
Mario Szegedy
A Slique Size Bounding Technique with Application to Non-Linear Codes. SODA (1999)
Mario Szegedy
Algorithms to Tile the Infinite Grid with Finite Clusters. FOCS (1998)
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
Proof Verification and the Hardness of Approximation Problems. J. ACM 45 (3) (1998)
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
Proof verification and the hardness of approximation problems. Electron. Colloquium Comput. Complex. 5 (8) (1998)
László Lovász, János Pach, Mario Szegedy
On Conway's Thrackle Conjecture. Discret. Comput. Geom. 18 (4) (1997)
Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy
Interactive Proofs and the Hardness of Approximating Cliques. J. ACM 43 (2) (1996)
János Pach, Farhad Shahrokhi, Mario Szegedy
Applications of the Crossing Number. Algorithmica 16 (1) (1996)
Noga Alon, Yossi Matias, Mario Szegedy
The Space Complexity of Approximating the Frequency Moments. STOC (1996)
Ilan Newman, Mario Szegedy
Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). STOC (1996)
László Lovász, János Pach, Mario Szegedy
On Conway's Thrackle Conjecture. SCG (1995)
Anna Gál, Mario Szegedy
Fault Tolerant Circuits and Probabilistically Checkable Proofs. Computational Complexity Conference (1995)
Magnús M. Halldórsson, Mario Szegedy
Lower Bounds for On-Line Graph Coloring. Theor. Comput. Sci. 130 (1) (1994)
Noam Nisan, Mario Szegedy
On the Degree of Boolean Functions as Real Polynomials. Comput. Complex. 4 (1994)
Mario Szegedy
A note on the Theta number of Lovász and the generalized Delsarte bound FOCS (1994)
János Pach, Farhad Shahrokhi, Mario Szegedy
Applications of the Crossing Number. SCG (1994)
Mario Szegedy, Sundar Vishwanathan
Locality based graph coloring. STOC (1993)
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) (1993)
Mario Szegedy
Functions with Bounded Symmetric Communication Complexity, Programs over Commutative Monoids, and ACC. J. Comput. Syst. Sci. 47 (3) (1993)
Lance Fortnow, Mario Szegedy
On the Power of Two-Local Random Reductions. Inf. Process. Lett. 44 (6) (1992)
László Babai, Mario Szegedy
Local Expansion of Ssymmetrical Graphs. Comb. Probab. Comput. 1 (1992)

Mario Szegedy.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Mario Szegedy