| 2009 |
|---|
| 74 | EE | 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 |
|---|
| 73 | EE | Kooshiar Azimian,
Mario Szegedy:
Parallel Repetition of the Odd Cycle Game.
LATIN 2008: 676-686 |
| 72 | EE | 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 |
| 71 | EE | Peter Richter,
Mario Szegedy:
Quantization of Markov Chains.
Encyclopedia of Algorithms 2008 |
| 2007 |
|---|
| 70 | EE | Mario Szegedy,
Mikkel Thorup:
On the Variance of Subset Sum Estimation.
ESA 2007: 75-86 |
| 69 | EE | Rajat Mittal,
Mario Szegedy:
Product Rules in Semidefinite Programming.
FCT 2007: 435-445 |
| 68 | EE | Arkadev Chattopadhyay,
Andreas Krebs,
Michal Koucký,
Mario Szegedy,
Pascal Tesson,
Denis Thérien:
Languages with Bounded Multiparty Communication Complexity.
STACS 2007: 500-511 |
| 67 | EE | Mario Szegedy,
Mikkel Thorup:
On the variance of subset sum estimation
CoRR abs/cs/0702029: (2007) |
| 66 | EE | Frédéric Magniez,
Miklos Santha,
Mario Szegedy:
Quantum Algorithms for the Triangle Problem.
SIAM J. Comput. 37(2): 413-424 (2007) |
| 2006 |
|---|
| 65 | EE | Su Chen,
Tomasz Imielinski,
Karin Johnsgard,
Donald Smith,
Mario Szegedy:
A Dichotomy Theorem for Typed Constraint Satisfaction Problems.
SAT 2006: 226-239 |
| 64 | EE | Mario Szegedy:
The DLT priority sampling is essentially optimal.
STOC 2006: 150-158 |
| 63 | EE | Sophie Laplante,
Troy Lee,
Mario Szegedy:
The Quantum Adversary Method and Classical Formula Size Lower Bounds.
Computational Complexity 15(2): 163-196 (2006) |
| 62 | EE | 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) |
| 61 | EE | Robert Spalek,
Mario Szegedy:
All Quantum Adversary Methods are Equivalent.
Theory of Computing 2(1): 1-18 (2006) |
| 2005 |
|---|
| 60 | EE | Xiaomin Chen,
Mario Szegedy,
Lei Wang:
Optimally Balanced Forward Degree Sequence.
COCOON 2005: 680-689 |
| 59 | EE | Robert Spalek,
Mario Szegedy:
All Quantum Adversary Methods Are Equivalent.
ICALP 2005: 1299-1311 |
| 58 | EE | Sophie Laplante,
Troy Lee,
Mario Szegedy:
The Quantum Adversary Method and Classical Formula Size Lower Bounds.
IEEE Conference on Computational Complexity 2005: 76-90 |
| 57 | EE | Frédéric Magniez,
Miklos Santha,
Mario Szegedy:
Quantum algorithms for the triangle problem.
SODA 2005: 1109-1117 |
| 56 | EE | Mario Szegedy:
Near optimality of the priority sampling procedure
Electronic Colloquium on Computational Complexity (ECCC)(001): (2005) |
| 2004 |
|---|
| 55 | EE | Mario Szegedy:
Quantum Speed-Up of Markov Chain Based Algorithms.
FOCS 2004: 32-41 |
| 54 | EE | Miklos Santha,
Mario Szegedy:
Quantum and classical query complexities of local search are polynomially related.
STOC 2004: 494-501 |
| 53 | EE | 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) |
| 52 | EE | Mario Szegedy,
Xiaomin Chen:
Computing Boolean functions from multiple faulty copies of input bits.
Theor. Comput. Sci. 321(1): 149-170 (2004) |
| 2003 |
|---|
| 51 | EE | Howard Barnum,
Michael E. Saks,
Mario Szegedy:
Quantum query complexity and semi-definite programming.
IEEE Conference on Computational Complexity 2003: 179-193 |
| 50 | EE | 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 |
|---|
| 49 | EE | Mario Szegedy,
Xiaomin Chen:
Computing Boolean Functions from Multiple Faulty Copies of Input Bits.
LATIN 2002: 539-553 |
| 48 | EE | 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 |
|---|
| 47 | EE | Noga Alon,
Eldar Fischer,
Mario Szegedy:
Parent-Identifying Codes.
J. Comb. Theory, Ser. A 95(2): 349-359 (2001) |
| 2000 |
|---|
| 46 | EE | Noga Alon,
Eldar Fischer,
Michael Krivelevich,
Mario Szegedy:
Efficient Testing of Large Graphs.
Combinatorica 20(4): 451-476 (2000) |
| 45 | EE | 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 |
|---|
| 44 | EE | Noga Alon,
Michael Krivelevich,
Ilan Newman,
Mario Szegedy:
Regular Languages Are Testable with a Constant Number of Queries.
FOCS 1999: 645-655 |
| 43 | EE | Noga Alon,
Eldar Fischer,
Michael Krivelevich,
Mario Szegedy:
Efficient Testing of Large Graphs.
FOCS 1999: 656-666 |
| 42 | EE | Mario Szegedy:
Many-Valued Logics and Holographic Proofs.
ICALP 1999: 676-686 |
| 41 | EE | Noga Alon,
Phillip B. Gibbons,
Yossi Matias,
Mario Szegedy:
Tracking Join and Self-Join Sizes in Limited Storage.
PODS 1999: 10-20 |
| 40 | EE | Haim Kaplan,
Mario Szegedy:
On-line Complexity of Monotone Set Systems.
SODA 1999: 507-516 |
| 39 | EE | David S. Johnson,
Mario Szegedy:
What are the Least Tractable Instances of max Tndependent Set?
SODA 1999: 927-928 |
| 38 | EE | Haim Kaplan,
Martin Strauss,
Mario Szegedy:
Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data.
SODA 1999: 935-936 |
| 37 | EE | Mario Szegedy:
A Slique Size Bounding Technique with Application to Non-Linear Codes.
SODA 1999: 971-972 |
| 36 | EE | Mario Szegedy:
In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved?
STACS 1999: 356-361 |
| 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 | EE | Mario Szegedy:
Algorithms to Tile the Infinite Grid with Finite Clusters.
FOCS 1998: 137-147 |
| 33 | EE | 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 | EE | 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 | EE | László Lovász,
János Pach,
Mario Szegedy:
On Conway's Thrackle Conjecture.
Discrete & Computational Geometry 18(4): 369-376 (1997) |
| 1996 |
|---|
| 30 | EE | Noga Alon,
Yossi Matias,
Mario Szegedy:
The Space Complexity of Approximating the Frequency Moments.
STOC 1996: 20-29 |
| 29 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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) |
