Travelled to:1 × Canada
1 × Czech Republic
1 × France
1 × Greece
1 × Portugal
1 × United Kingdom
11 × USA
Collaborated with:∅ N.Nisan N.Alon Y.Matias L.Babai M.M.Halldórsson K.B.R.Kolipaka J.Roland G.Kun R.Spalek M.Santha I.Newman S.Vishwanathan J.Simon X.Sun C.Wang B.V.Halldórsson E.Losievskaja P.B.Gibbons L.Fortnow L.A.Levin S.Chen T.Imielinski K.Johnsgard D.Smith
Talks about:complex (6) communic (4) dichotomi (2) polynomi (2) function (2) approxim (2) quantum (2) stream (2) local (2) join (2)
Person: Mario Szegedy
DBLP: Szegedy:Mario
Contributed to:
2012
2011201020092009
20062006200520041999
1999199619931992199119901989Wrote 19 papers:
- ICALP-v1-2012-HalldorssonSSW #approximate #clique #communication #complexity #streaming
- Streaming and Communication Complexity of Clique Approximation (MMH, XS, MS, CW), pp. 449–460.
- STOC-2011-KolipakaS
- Moser and tardos meet Lovász (KBRK, MS), pp. 235–244.
- ICALP-v1-2010-HalldorssonHLS #algorithm #independence #set #streaming
- Streaming Algorithms for Independent Sets (BVH, MMH, EL, MS), pp. 641–652.
- ICALP-v1-2009-RolandS #communication #complexity
- Amortized Communication Complexity of Distributions (JR, MS), pp. 738–749.
- STOC-2009-KunS
- A new line of attack on the dichotomy conjecture (GK, MS), pp. 725–734.
- SAT-2006-ChenIJSS #constraints #problem #theorem
- A Dichotomy Theorem for Typed Constraint Satisfaction Problems (SC, TI, KJ, DS, MS), pp. 226–239.
- STOC-2006-Szegedy
- The DLT priority sampling is essentially optimal (MS), pp. 150–158.
- ICALP-2005-SpalekS #quantum
- All Quantum Adversary Methods Are Equivalent (RS, MS), pp. 1299–1311.
- STOC-2004-SanthaS #quantum #query
- Quantum and classical query complexities of local search are polynomially related (MS, MS), pp. 494–501.
- ICALP-1999-Szegedy #artificial reality #logic #proving
- Many-Valued Logics and Holographic Proofs (MS), pp. 676–686.
- PODS-1999-AlonGMS #self
- Tracking Join and Self-Join Sizes in Limited Storage (NA, PBG, YM, MS), pp. 10–20.
- STOC-1996-AlonMS #approximate #complexity
- The Space Complexity of Approximating the Frequency Moments (NA, YM, MS), pp. 20–29.
- STOC-1996-NewmanS #communication #game studies
- Public vs. Private Coin Flips in One Round Communication Games (IN, MS), pp. 561–570.
- STOC-1993-SzegedyV #graph #locality
- Locality based graph coloring (MS, SV), pp. 201–207.
- STOC-1992-NisanS #on the
- On the Degree of Boolean Functions as Real Polynomials (NN, MS), pp. 462–467.
- STOC-1992-SimonS #complexity #on the #ram #set
- On the Complexity of RAM with Various Operation Sets (JS, MS), pp. 624–631.
- STOC-1991-BabaiFLS
- Checking Computations in Polylogarithmic Time (LB, LF, LAL, MS), pp. 21–31.
- STOC-1990-Szegedy #bound #communication #complexity #symmetry
- Functions with Bounded Symmetric Communication Complexity and Circuits with mod m Gates (MS), pp. 278–286.
- STOC-1989-BabaiNS #multi #protocol #pseudo #sequence
- Multiparty Protocols and Logspace-hard Pseudorandom Sequences (LB, NN, MS), pp. 1–11.