Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMario 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
showing all ?? records
2020 – today
- 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 Cross, Zhiyang He, Anand Natarajan, Mario Szegedy, Guanyu Zhu:
Quantum Locally Testable Code with Exotic Parameters. CoRR abs/2209.11405 (2022) - 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, Ser. 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)