Mario Szegedy

	2011
85		Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy: Quantum Query Complexity of State Conversion. FOCS 2011: 344-353
84		Kashyap Babu Rao Kolipaka, Mario Szegedy: Moser and tardos meet Lovász. STOC 2011: 235-244
83		Ákos Seress, Mario Szegedy: Combinatorics, Groups, Algorithms, and Complexity: Conference in honor of Laci Babai's 60th birthday. Discrete Mathematics & Theoretical Computer Science 13(4): 1-4 (2011)
	2010
82		William Steiger, Mario Szegedy, Jihui Zhao: Six-way equipartitioning by three lines in the plane. CCCG 2010: 277-280
81		Bjarni V. Halldórsson, Magnús M. Halldórsson, Elena Losievskaja, Mario Szegedy: Streaming Algorithms for Independent Sets. ICALP (1) 2010: 641-652
	2009
80		Jérémie Roland, Mario Szegedy: Amortized Communication Complexity of Distributions. ICALP (1) 2009: 738-749
79		Gábor Kun, Mario Szegedy: A new line of attack on the dichotomy conjecture. STOC 2009: 725-734
78		Miklos Santha, Mario Szegedy: Quantum and Classical Query Complexities of Local Search Are Polynomially Related. Algorithmica 55(3): 557-575 (2009)
77		Padmini Mukkamala, Mario Szegedy: Geometric representation of cubic graphs with four directions. Comput. Geom. 42(9): 842-851 (2009)
76		Gábor Kun, Mario Szegedy: A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE. Electronic Colloquium on Computational Complexity (ECCC) 16: 59 (2009)
75		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)
	2008
74		Kooshiar Azimian, Mario Szegedy: Parallel Repetition of the Odd Cycle Game. LATIN 2008: 676-686
73		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
72		Peter Richter, Mario Szegedy: Quantization of Markov Chains. Encyclopedia of Algorithms 2008
	2007
71		Mario Szegedy, Mikkel Thorup: On the Variance of Subset Sum Estimation. ESA 2007: 75-86
70		Rajat Mittal, Mario Szegedy: Product Rules in Semidefinite Programming. FCT 2007: 435-445
69		Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien: Languages with Bounded Multiparty Communication Complexity. STACS 2007: 500-511
68		Mario Szegedy, Mikkel Thorup: On the variance of subset sum estimation CoRR abs/cs/0702029: (2007)
67		Frédéric Magniez, Miklos Santha, Mario Szegedy: Quantum Algorithms for the Triangle Problem. SIAM J. Comput. 37(2): 413-424 (2007)
	2006
66		Su Chen, Tomasz Imielinski, Karin Johnsgard, Donald Smith, Mario Szegedy: A Dichotomy Theorem for Typed Constraint Satisfaction Problems. SAT 2006: 226-239
65		Mario Szegedy: The DLT priority sampling is essentially optimal. STOC 2006: 150-158
64		Sophie Laplante, Troy Lee, Mario Szegedy: The Quantum Adversary Method and Classical Formula Size Lower Bounds. Computational Complexity 15(2): 163-196 (2006)
63		Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien: Languages with Bounded Multiparty Communication Complexity. Electronic Colloquium on Computational Complexity (ECCC) 13(117): (2006)
62		Robert Spalek, Mario Szegedy: All Quantum Adversary Methods are Equivalent. Theory of Computing 2(1): 1-18 (2006)
	2005
61		Xiaomin Chen, Mario Szegedy, Lei Wang: Optimally Balanced Forward Degree Sequence. COCOON 2005: 680-689
60		Robert Spalek, Mario Szegedy: All Quantum Adversary Methods Are Equivalent. ICALP 2005: 1299-1311
59		Sophie Laplante, Troy Lee, Mario Szegedy: The Quantum Adversary Method and Classical Formula Size Lower Bounds. IEEE Conference on Computational Complexity 2005: 76-90
58		Frédéric Magniez, Miklos Santha, Mario Szegedy: Quantum algorithms for the triangle problem. SODA 2005: 1109-1117
57		Mario Szegedy: Near optimality of the priority sampling procedure Electronic Colloquium on Computational Complexity (ECCC)(001): (2005)
	2004
56		Mario Szegedy: Quantum Speed-Up of Markov Chain Based Algorithms. FOCS 2004: 32-41
55		Miklos Santha, Mario Szegedy: Quantum and classical query complexities of local search are polynomially related. STOC 2004: 494-501
54		József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy: Long Monotone Paths in Line Arrangements. Discrete & Computational Geometry 32(2): 167-176 (2004)
53		Mario Szegedy, Xiaomin Chen: Computing Boolean functions from multiple faulty copies of input bits. Theor. Comput. Sci. 321(1): 149-170 (2004)
	2003
52		Howard Barnum, Michael E. Saks, Mario Szegedy: Quantum query complexity and semi-definite programming. IEEE Conference on Computational Complexity 2003: 179-193
51		József Balogh, Oded Regev, Clifford D. Smyth, William L. Steiger, Mario Szegedy: Long monotone paths in line arrangements. Symposium on Computational Geometry 2003: 124-128
	2002
50		Mario Szegedy, Xiaomin Chen: Computing Boolean Functions from Multiple Faulty Copies of Input Bits. LATIN 2002: 539-553
49		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)
	2001
48		Noga Alon, Eldar Fischer, Mario Szegedy: Parent-Identifying Codes. J. Comb. Theory, Ser. A 95(2): 349-359 (2001)
	2000
47		Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy: Efficient Testing of Large Graphs. Combinatorica 20(4): 451-476 (2000)
46		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)
	1999
45		Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy: Regular Languages Are Testable with a Constant Number of Queries. FOCS 1999: 645-655
44		Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy: Efficient Testing of Large Graphs. FOCS 1999: 656-666
43		Mario Szegedy: Many-Valued Logics and Holographic Proofs. ICALP 1999: 676-686
42		Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy: Tracking Join and Self-Join Sizes in Limited Storage. PODS 1999: 10-20
41		Haim Kaplan, Mario Szegedy: On-line Complexity of Monotone Set Systems. SODA 1999: 507-516
40		David S. Johnson, Mario Szegedy: What are the Least Tractable Instances of max Tndependent Set? SODA 1999: 927-928
39		Haim Kaplan, Martin Strauss, Mario Szegedy: Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data. SODA 1999: 935-936
38		Mario Szegedy: A Slique Size Bounding Technique with Application to Non-Linear Codes. SODA 1999: 971-972
37		Mario Szegedy: In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved? STACS 1999: 356-361
36		Noga Alon, Mario Szegedy: Large Sets of Nearly Orthogonal Vectors. Graphs and Combinatorics 15(1): 1-4 (1999)
35		Noga Alon, Yossi Matias, Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci. 58(1): 137-147 (1999)
	1998
34		Mario Szegedy: Algorithms to Tile the Infinite Grid with Finite Clusters. FOCS 1998: 137-147
33		Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof verification and the hardness of approximation problems. Electronic Colloquium on Computational Complexity (ECCC) 5(8): (1998)
32		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)
	1997
31		László Lovász, János Pach, Mario Szegedy: On Conway's Thrackle Conjecture. Discrete & Computational Geometry 18(4): 369-376 (1997)
	1996
30		Noga Alon, Yossi Matias, Mario Szegedy: The Space Complexity of Approximating the Frequency Moments. STOC 1996: 20-29
29		Ilan Newman, Mario Szegedy: Public vs. Private Coin Flips in One Round Communication Games (Extended Abstract). STOC 1996: 561-570
28		János Pach, Farhad Shahrokhi, Mario Szegedy: Applications of the Crossing Number. Algorithmica 16(1): 111-117 (1996)
27		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)
	1995
26		Anna Gál, Mario Szegedy: Fault Tolerant Circuits and Probabilistically Checkable Proofs. Structure in Complexity Theory Conference 1995: 65-73
25		László Lovász, János Pach, Mario Szegedy: On Conway's Thrackle Conjecture. Symposium on Computational Geometry 1995: 147-151
	1994
24		Mario Szegedy: A note on the Theta number of Lovász and the generalized Delsarte bound FOCS 1994: 36-39
23		János Pach, Farhad Shahrokhi, Mario Szegedy: Applications of the Crossing Number. Symposium on Computational Geometry 1994: 198-202
22		Noam Nisan, Mario Szegedy: On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4: 301-313 (1994)
21		Magnús M. Halldórsson, Mario Szegedy: Lower Bounds for On-Line Graph Coloring. Theor. Comput. Sci. 130(1): 163-174 (1994)
	1993
20		Mario Szegedy, Sundar Vishwanathan: Locality based graph coloring. STOC 1993: 201-207
19		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)
18		Mario Szegedy: Functions with Bounded Symmetric Communication Complexity, Programs over Commutative Monoids, and ACC. J. Comput. Syst. Sci. 47(3): 405-423 (1993)
	1992
17		Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof Verification and Hardness of Approximation Problems FOCS 1992: 14-23
16		Magnús M. Halldórsson, Mario Szegedy: Lower Bounds for On-Line Graph Coloring. SODA 1992: 211-216
15		Noam Nisan, Mario Szegedy: On the Degree of Boolean Functions as Real Polynomials STOC 1992: 462-467
14		Janos Simon, Mario Szegedy: On the Complexity of RAM with Various Operation Sets STOC 1992: 624-631
13		Péter Hajnal, Mario Szegedy: On packing bipartite graphs. Combinatorica 12(3): 295-301 (1992)
12		László Babai, Mario Szegedy: Local Expansion of Ssymmetrical Graphs. Combinatorics, Probability & Computing 1: 1-11 (1992)
11		Lance Fortnow, Mario Szegedy: On the Power of Two-Local Random Reductions. Inf. Process. Lett. 44(6): 303-306 (1992)
10		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)
	1991
9		Lance Fortnow, Mario Szegedy: On the Power of Two-Local Random Reductions. ASIACRYPT 1991: 346-351
8		Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy: Approximating Clique is Almost NP-Complete (Preliminary Version) FOCS 1991: 2-12
7		László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy: Checking Computations in Polylogarithmic Time STOC 1991: 21-31
	1990
6		Mario Szegedy: Functions with Bounded Symmetric Communication Complexity and Circuits with \mathop mod m Gates STOC 1990: 278-286
	1989
5		László Babai, Noam Nisan, Mario Szegedy: Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract) STOC 1989: 1-11
	1988
4		David Rubinstein, Jeffrey Shallit, Mario Szegedy: A Subset Coloring Algorithm and Its Applications to Computer Graphics. Commun. ACM 31(10): 1228-1232 (1988)
	1987
3		András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán: Threshold circuits of bounded depth FOCS 1987: 99-110
	1986
2		Mario Szegedy: The solution of Graham's greatest common divisor problem. Combinatorica 6(1): 67-71 (1986)
	1984
1		Gustav Burosch, Waleri Wassiljewitsch Gorlow, Roger Labahn, Mario Szegedy: The Telephone Problem for Connected Graphs. Elektronische Informationsverarbeitung und Kybernetik 20(10/11): 557-573 (1984)

Coauthor Index

1	Noga Alon	[30] [35] [36] [42] [44] [45] [46] [47] [48] [49]
2	Sanjeev Arora	[17] [32] [33]
3	Kooshiar Azimian	[74]
4	László Babai	[5] [7] [10] [12]
5	József Balogh	[51] [54]
6	Howard Barnum	[52]
7	Gustav Burosch	[1]
8	Arkadev Chattopadhyay	[63] [69]
9	Su Chen	[66]
10	Xiaomin Chen	[50] [53] [61] [73] [75]
11	Uriel Feige	[8] [27]
12	Eldar Fischer	[44] [47] [48]
13	Lance Fortnow	[7] [9] [11]
14	Anna Gál	[26]
15	Phillip B. Gibbons	[42] [49]
16	Shafi Goldwasser	[8] [27]
17	Waleri Wassiljewitsch Gorlow	[1]
18	András Hajnal	[3] [19]
19	Péter Hajnal	[13]
20	Bjarni V. Halldórsson	[81]
21	Magnús M. Halldórsson	[16] [21] [81]
22	Tomasz Imielinski	[66]
23	Karin Johnsgard	[66]
24	David S. Johnson	[40]
25	Haim Kaplan	[39] [41]
26	Kashyap Babu Rao Kolipaka	[84]
27	Michal Koucký	[63] [69]
28	Andreas Krebs	[63] [69]
29	Michael Krivelevich	[44] [45] [46] [47]
30	Gábor Kun	[76] [79]
31	Roger Labahn	[1]
32	Sophie Laplante	[59] [64]
33	Troy Lee	[59] [64] [85]
34	Leonid A. Levin	[7]
35	Elena Losievskaja	[81]
36	László Lovász	[8] [25] [27] [31]
37	Carsten Lund	[17] [32] [33]
38	Wolfgang Maass	[3] [19]
39	Frédéric Magniez	[58] [67]
40	Yossi Matias	[30] [35] [42] [49]
41	Rajat Mittal	[70] [85]
42	Rajeev Motwani	[17] [32] [33]
43	Padmini Mukkamala	[77]
44	Ilan Newman	[29] [45] [46]
45	Noam Nisan	[5] [10] [15] [22]
46	János Pach	[23] [25] [28] [31] [73] [75]
47	Pavel Pudlák	[3] [19]
48	Oded Regev	[51] [54]
49	Ben Reichardt (Ben W. Reichardt)	[85]
50	Peter Richter	[72]
51	Jérémie Roland	[80]
52	David Rubinstein	[4]
53	Shmuel Safra (Muli Safra)	[8] [27]
54	Michael E. Saks (Michael Saks)	[52]
55	Miklos Santha	[55] [58] [67] [78]
56	Ákos Seress	[83]
57	Farhad Shahrokhi	[23] [28]
58	Jeffrey Shallit (Jeffrey O. Shallit)	[4]
59	Janos Simon	[14]
60	Donald Smith	[66]
61	Clifford D. Smyth	[51] [54]
62	Robert Spalek	[60] [62] [85]
63	William Steiger	[82]
64	William L. Steiger	[51] [54]
65	Martin Strauss (Martin J. Strauss)	[39]
66	Madhu Sudan	[17] [32] [33]
67	Gábor Tardos	[73] [75]
68	Pascal Tesson	[63] [69]
69	Denis Thérien	[63] [69]
70	Mikkel Thorup	[68] [71]
71	György Turán	[3] [19]
72	Sundar Vishwanathan	[20]
73	Lei Wang	[61]
74	Jihui Zhao	[82]

Colors in the list of coauthors

Last update Fri May 25 01:42:58 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page