default search action
Mario Szegedy
Person information
- affiliation: Rutgers University, New Brunswick, NJ, USA
- award (2019): ACM Paris Kanellakis Theory and Practice Award
- award (2001,2005): Gödel Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2023
- [j37]Mario Szegedy, Jingjin Yu:
An Initial Study of Budgeted Steiner Networks. Comput. Geom. Topol. 2(2): 4:1-4:13 (2023) - [j36]Mario Szegedy, Jingjin Yu:
Rubik Tables and object rearrangement. Int. J. Robotics Res. 42(6): 459-472 (2023) - 2022
- [b1]Mario Szegedy, Ilan Newman, Troy Lee:
Query Complexity. WorldScientific 2022, ISBN 9789813223202, pp. 1-200 - [c64]Teng Guo, Si Wei Feng, Mario Szegedy, Jingjin Yu:
Rubik Tables, Stack Rearrangement, and Multi-Robot Path Planning. Allerton 2022: 1-4 - [c63]Jingjin Yu, Mario Szegedy:
Budgeted Steiner Networks: Three Terminals with Equal Path Weights. CCCG 2022: 322-329 - [i16]Mario Szegedy, Jingjin Yu:
Budgeted Steiner Networks: Three Terminals with Equal Path Weights. CoRR abs/2201.11602 (2022) - [i15]Ramis Movassagh, Mario Szegedy, Guanyang Wang:
Repeated Averages on Graphs. CoRR abs/2205.04535 (2022) - [i14]Andrew W. Cross, Zhiyang He, Anand Natarajan, Mario Szegedy, Guanyu Zhu:
Quantum Locally Testable Code with Exotic Parameters. CoRR abs/2209.11405 (2022) - 2021
- [j35]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): 578-587 (2021) - [c62]Mario Szegedy, Jingjin Yu:
On Rearrangement of Items Stored in Stacks. WAFR 2021: 518-533 - 2020
- [j34]Cupjin Huang, Michael Newman, Mario Szegedy:
Explicit Lower Bounds on Strong Quantum Simulation. IEEE Trans. Inf. Theory 66(9): 5585-5600 (2020) - [i13]Mario Szegedy, Jingjin Yu:
On Rearrangement of Items Stored in Stacks. CoRR abs/2002.04979 (2020)
2010 – 2019
- 2019
- [i12]Cupjin Huang, Michael Newman, Mario Szegedy:
Explicit lower bounds on strong simulation of quantum circuits in terms of $T$-gate count. CoRR abs/1902.04764 (2019) - 2018
- [i11]Cupjin Huang, Michael Newman, Mario Szegedy:
Explicit lower bounds on strong quantum simulation. CoRR abs/1804.10368 (2018) - 2017
- [j33]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): 14:1-14:21 (2017) - [c61]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: 159-171 - [c60]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: 6 - 2016
- [j32]Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, Mario Szegedy:
Streaming Algorithms for Independent Sets in Sparse Hypergraphs. Algorithmica 76(2): 490-501 (2016) - [j31]Gábor Kun, Mario Szegedy:
A new line of attack on the dichotomy conjecture. Eur. J. Comb. 52: 338-367 (2016) - [r3]Ashwin Nayak, Peter C. Richter, Mario Szegedy:
Quantum Analogues of Markov Chains. Encyclopedia of Algorithms 2016: 1683-1691 - [i10]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 abs/1605.02043 (2016) - 2015
- [i9]Mario Szegedy, Yixin Xu:
Impossibility Theorems and the Universal Algebraic Toolkit. CoRR abs/1506.01315 (2015) - [i8]Mario Szegedy:
An $O(n^{0.4732})$ upper bound on the complexity of the GKS communication game. CoRR abs/1506.06456 (2015) - 2014
- [c59]Well Y. Chiu, Mario Szegedy, Chengu Wang, Yixin Xu:
The Garden Hose Complexity for the Equality Function. AAIM 2014: 112-123 - [c58]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: 246-255 - 2013
- [c57]Eike Kiltz, Krzysztof Pietrzak, Mario Szegedy:
Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions. CRYPTO (1) 2013: 571-588 - [c56]Mario Szegedy:
The Lovász Local Lemma - A Survey. CSR 2013: 1-11 - [i7]Well Y. Chiu, Mario Szegedy, Chengu Wang, Yixin Xu:
The Garden Hose Complexity for the Equality Function. CoRR abs/1312.7222 (2013) - 2012
- [c55]Kashyap Babu Rao Kolipaka, Mario Szegedy, Yixin Xu:
A Sharper Local Lemma with Improved Applications. APPROX-RANDOM 2012: 603-614 - [c54]Matthias Poloczek, Mario Szegedy:
Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis. FOCS 2012: 708-717 - [c53]Magnús M. Halldórsson, Xiaoming Sun, Mario Szegedy, Chengu Wang:
Streaming and Communication Complexity of Clique Approximation. ICALP (1) 2012: 449-460 - [c52]Ioannis Caragiannis, Edith Elkind, Mario Szegedy, Lan Yu:
Mechanism design: from partial to probabilistic verification. EC 2012: 266-283 - [i6]Eike Kiltz, Krzysztof Pietrzak, Mario Szegedy:
Digital Signatures with Minimal Overhead. IACR Cryptol. ePrint Arch. 2012: 658 (2012) - 2011
- [j30]Á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): 1-4 (2011) - [c51]Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy:
Quantum Query Complexity of State Conversion. FOCS 2011: 344-353 - [c50]Kashyap Babu Rao Kolipaka, Mario Szegedy:
Moser and tardos meet Lovász. STOC 2011: 235-244 - 2010
- [c49]William Steiger, Mario Szegedy, Jihui Zhao:
Six-way equipartitioning by three lines in the plane. CCCG 2010: 277-280 - [c48]Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, Mario Szegedy:
Streaming Algorithms for Independent Sets. ICALP (1) 2010: 641-652
2000 – 2009
- 2009
- [j29]Miklos Santha, Mario Szegedy:
Quantum and Classical Query Complexities of Local Search Are Polynomially Related. Algorithmica 55(3): 557-575 (2009) - [j28]Padmini Mukkamala, Mario Szegedy:
Geometric representation of cubic graphs with four directions. Comput. Geom. 42(9): 842-851 (2009) - [j27]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) - [c47]Jérémie Roland, Mario Szegedy:
Amortized Communication Complexity of Distributions. ICALP (1) 2009: 738-749 - [c46]Gábor Kun, Mario Szegedy:
A new line of attack on the dichotomy conjecture. STOC 2009: 725-734 - [i5]Gábor Kun, Mario Szegedy:
A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [c45]Kooshiar Azimian, Mario Szegedy:
Parallel Repetition of the Odd Cycle Game. LATIN 2008: 676-686 - [c44]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 - [r2]Peter C. Richter, Mario Szegedy:
Quantization of Markov Chains. Encyclopedia of Algorithms 2008 - 2007
- [j26]Frédéric Magniez, Miklos Santha, Mario Szegedy:
Quantum Algorithms for the Triangle Problem. SIAM J. Comput. 37(2): 413-424 (2007) - [c43]Mario Szegedy, Mikkel Thorup:
On the Variance of Subset Sum Estimation. ESA 2007: 75-86 - [c42]Rajat Mittal, Mario Szegedy:
Product Rules in Semidefinite Programming. FCT 2007: 435-445 - [c41]Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien:
Languages with Bounded Multiparty Communication Complexity. STACS 2007: 500-511 - [r1]Mario Szegedy:
Hardness of Approximation. Handbook of Approximation Algorithms and Metaheuristics 2007 - [i4]Mario Szegedy, Mikkel Thorup:
On the variance of subset sum estimation. CoRR abs/cs/0702029 (2007) - 2006
- [j25]Sophie Laplante, Troy Lee, Mario Szegedy:
The Quantum Adversary Method and Classical Formula Size Lower Bounds. Comput. Complex. 15(2): 163-196 (2006) - [j24]Robert Spalek, Mario Szegedy:
All Quantum Adversary Methods are Equivalent. Theory Comput. 2(1): 1-18 (2006) - [c40]Su Chen, Tomasz Imielinski, Karin Johnsgard, Donald Smith, Mario Szegedy:
A Dichotomy Theorem for Typed Constraint Satisfaction Problems. SAT 2006: 226-239 - [c39]Mario Szegedy:
The DLT priority sampling is essentially optimal. STOC 2006: 150-158 - [i3]Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien:
Languages with Bounded Multiparty Communication Complexity. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [c38]Sophie Laplante, Troy Lee, Mario Szegedy:
The Quantum Adversary Method and Classical Formula Size Lower Bounds. CCC 2005: 76-90 - [c37]Xiaomin Chen, Mario Szegedy, Lei Wang:
Optimally Balanced Forward Degree Sequence. COCOON 2005: 680-689 - [c36]Robert Spalek, Mario Szegedy:
All Quantum Adversary Methods Are Equivalent. ICALP 2005: 1299-1311 - [c35]Frédéric Magniez, Miklos Santha, Mario Szegedy:
Quantum algorithms for the triangle problem. SODA 2005: 1109-1117 - [i2]Mario Szegedy:
Near optimality of the priority sampling procedure. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j23]József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy:
Long Monotone Paths in Line Arrangements. Discret. Comput. Geom. 32(2): 167-176 (2004) - [j22]Mario Szegedy, Xiaomin Chen:
Computing Boolean functions from multiple faulty copies of input bits. Theor. Comput. Sci. 321(1): 149-170 (2004) - [c34]Mario Szegedy:
Quantum Speed-Up of Markov Chain Based Algorithms. FOCS 2004: 32-41 - [c33]Miklos Santha, Mario Szegedy:
Quantum and classical query complexities of local search are polynomially related. STOC 2004: 494-501 - 2003
- [c32]Howard Barnum, Michael E. Saks, Mario Szegedy:
Quantum query complexity and semi-definite programming. CCC 2003: 179-193 - [c31]József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy:
Long monotone paths in line arrangements. SCG 2003: 124-128 - 2002
- [j21]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) - [c30]Mario Szegedy, Xiaomin Chen:
Computing Boolean Functions from Multiple Faulty Copies of Input Bits. LATIN 2002: 539-553 - 2001
- [j20]Noga Alon, Eldar Fischer, Mario Szegedy:
Parent-Identifying Codes. J. Comb. Theory A 95(2): 349-359 (2001) - 2000
- [j19]Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy:
Efficient Testing of Large Graphs. Comb. 20(4): 451-476 (2000) - [j18]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)
1990 – 1999
- 1999
- [j17]Noga Alon, Mario Szegedy:
Large Sets of Nearly Orthogonal Vectors. Graphs Comb. 15(1): 1-4 (1999) - [j16]Noga Alon, Yossi Matias, Mario Szegedy:
The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci. 58(1): 137-147 (1999) - [c29]Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy:
Regular Languages Are Testable with a Constant Number of Queries. FOCS 1999: 645-655 - [c28]Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy:
Efficient Testing of Large Graphs. FOCS 1999: 656-666 - [c27]Mario Szegedy:
Many-Valued Logics and Holographic Proofs. ICALP 1999: 676-686 - [c26]Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy:
Tracking Join and Self-Join Sizes in Limited Storage. PODS 1999: 10-20 - [c25]Haim Kaplan, Mario Szegedy:
On-line Complexity of Monotone Set Systems. SODA 1999: 507-516 - [c24]David S. Johnson, Mario Szegedy:
What are the Least Tractable Instances of max Independent Set? SODA 1999: 927-928 - [c23]Haim Kaplan, Martin Strauss, Mario Szegedy:
Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data. SODA 1999: 935-936 - [c22]Mario Szegedy:
A Slique Size Bounding Technique with Application to Non-Linear Codes. SODA 1999: 971-972 - [c21]Mario Szegedy:
In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved? STACS 1999: 356-361 - 1998
- [j15]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) - [c20]Mario Szegedy:
Algorithms to Tile the Infinite Grid with Finite Clusters. FOCS 1998: 137-147 - [i1]Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy:
Proof verification and the hardness of approximation problems. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [j14]László Lovász, János Pach, Mario Szegedy:
On Conway's Thrackle Conjecture. Discret. Comput. Geom. 18(4): 369-376 (1997) - 1996
- [j13]János Pach, Farhad Shahrokhi, Mario Szegedy:
Applications of the Crossing Number. Algorithmica 16(1): 111-117 (1996) - [j12]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) - [c19]Noga Alon, Yossi Matias, Mario Szegedy:
The Space Complexity of Approximating the Frequency Moments. STOC 1996: 20-29 - [c18]Ilan Newman, Mario Szegedy:
Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). STOC 1996: 561-570 - 1995
- [c17]Anna Gál, Mario Szegedy:
Fault Tolerant Circuits and Probabilistically Checkable Proofs. SCT 1995: 65-73 - [c16]László Lovász, János Pach, Mario Szegedy:
On Conway's Thrackle Conjecture. SCG 1995: 147-151 - 1994
- [j11]Noam Nisan, Mario Szegedy:
On the Degree of Boolean Functions as Real Polynomials. Comput. Complex. 4: 301-313 (1994) - [j10]Magnús M. Halldórsson, Mario Szegedy:
Lower Bounds for On-Line Graph Coloring. Theor. Comput. Sci. 130(1): 163-174 (1994) - [c15]János Pach, Farhad Shahrokhi, Mario Szegedy:
Applications of the Crossing Number. SCG 1994: 198-202 - [c14]Mario Szegedy:
A note on the Theta number of Lovász and the generalized Delsarte bound. FOCS 1994: 36-39 - 1993
- [j9]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) - [j8]Mario Szegedy:
Functions with Bounded Symmetric Communication Complexity, Programs over Commutative Monoids, and ACC. J. Comput. Syst. Sci. 47(3): 405-423 (1993) - [c13]Mario Szegedy, Sundar Vishwanathan:
Locality based graph coloring. STOC 1993: 201-207 - 1992
- [j7]Péter Hajnal, Mario Szegedy:
On packing bipartite graphs. Comb. 12(3): 295-301 (1992) - [j6]László Babai, Mario Szegedy:
Local Expansion of Ssymmetrical Graphs. Comb. Probab. Comput. 1: 1-11 (1992) - [j5]Lance Fortnow, Mario Szegedy:
On the Power of Two-Local Random Reductions. Inf. Process. Lett. 44(6): 303-306 (1992) - [j4]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) - [c12]Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy:
Proof Verification and Hardness of Approximation Problems. FOCS 1992: 14-23 - [c11]Magnús M. Halldórsson, Mario Szegedy:
Lower Bounds for On-Line Graph Coloring. SODA 1992: 211-216 - [c10]Noam Nisan, Mario Szegedy:
On the Degree of Boolean Functions as Real Polynomials. STOC 1992: 462-467 - [c9]Janos Simon, Mario Szegedy:
On the Complexity of RAM with Various Operation Sets. STOC 1992: 624-631 - 1991
- [c8]Lance Fortnow, Mario Szegedy:
On the Power of Two-Local Random Reductions. ASIACRYPT 1991: 346-351 - [c7]Magnús M. Halldórsson, Mario Szegedy:
Lower Bounds for On-line Graph Coloring. On-Line Algorithms 1991: 169-179 - [c6]Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy:
Approximating Clique is Almost NP-Complete (Preliminary Version). FOCS 1991: 2-12 - [c5]László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy:
Checking Computations in Polylogarithmic Time. STOC 1991: 21-31 - 1990
- [c4]Janos Simon, Mario Szegedy:
A New Lower Bound Theorem for Read-Only-Once Branching Programs and its Applications. Advances In Computational Complexity Theory 1990: 183-193 - [c3]Mario Szegedy:
Functions with Bounded Symmetric Communication Complexity and Circuits with \mathop mod m Gates. STOC 1990: 278-286
1980 – 1989
- 1989
- [c2]László Babai, Noam Nisan, Mario Szegedy:
Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract). STOC 1989: 1-11 - 1988
- [j3]David Rubinstein, Jeffrey O. Shallit, Mario Szegedy:
A Subset Coloring Algorithm and Its Applications to Computer Graphics. Commun. ACM 31(10): 1228-1232 (1988) - 1987
- [c1]András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán:
Threshold circuits of bounded depth. FOCS 1987: 99-110 - 1986
- [j2]Mario Szegedy:
The solution of Graham's greatest common divisor problem. Comb. 6(1): 67-71 (1986) - 1984
- [j1]Gustav Burosch, Waleri Wassiljewitsch Gorlow, Roger Labahn, Mario Szegedy:
The Telephone Problem for Connected Graphs. J. Inf. Process. Cybern. 20(10/11): 557-573 (1984)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from , , and to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-05 21:12 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint