Travelled to:1 × Denmark
1 × Latvia
2 × Canada
9 × USA
Collaborated with:N.Linial J.Bulánek M.Koucký R.Paturi D.Zuckerman X.Sun F.Zaharoglou M.L.Fredman J.Kahn S.Kopparty M.Kumar A.Russell A.Magen F.Zane A.Srinivasan S.Zhou R.Impagliazzo A.Borodin D.Lichtenstein P.Beame R.M.Karp T.Pitassi M.Luby B.Awerbuch B.Patt-Shamir D.Peleg
Talks about:lower (4) bound (4) random (3) onlin (3) label (3) polynomi (2) complex (2) circuit (2) metric (2) effici (2)
Person: Michael E. Saks
DBLP: Saks:Michael_E=
Contributed to:
20142013
20122002199919981997199519931992198919871984Wrote 17 papers:
- ICALP-v1-2014-KoppartyKS #finite #performance
- Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields (SK, MK, MES), pp. 726–737.
- ICALP-v1-2013-BulanekKS #on the #online #random
- On Randomized Online Labeling with Polynomially Many Labels (JB, MK, MES), pp. 291–302.
- STOC-2012-BulanekKS #bound #online #problem
- Tight lower bounds for the online labeling problem (JB, MK, MES), pp. 1185–1198.
- STOC-2002-SaksS #approximate #bound #data type #distance
- Space lower bounds for distance approximation in the data stream model (MES, XS), pp. 360–369.
- STOC-1999-RussellSZ #bound
- Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model (AR, MES, DZ), pp. 339–347.
- STOC-1998-BeameKPS #complexity #on the #proving #random #satisfiability
- On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas (PB, RMK, TP, MES), pp. 561–571.
- STOC-1998-LinialMS #metric
- Trees and Euclidean Metrics (NL, AM, MES), pp. 169–175.
- STOC-1997-PaturiSZ #bound #exponential
- Exponential Lower Bounds for Depth 3 Boolean Circuits (RP, MES, FZ), pp. 86–91.
- STOC-1995-SaksSZ
- Explicit dispersers with polylog degree (MES, AS, SZ), pp. 479–488.
- STOC-1993-ImpagliazzoPS #trade-off
- Size-depth trade-offs for threshold circuits (RI, RP, MES), pp. 541–550.
- STOC-1993-LinialLSZ #combinator #performance #set
- Efficient construction of a small hitting set for combinatorial rectangles in high dimension (NL, ML, MES, DZ), pp. 258–267.
- STOC-1993-SaksZ
- Wait-free k-set agreement is impossible: the topology of public knowledge (MES, FZ), pp. 101–110.
- STOC-1992-AwerbuchPPS #adaptation #network
- Adapting to Asynchronous Dynamic Networks (BA, BPS, DP, MES), pp. 557–570.
- STOC-1989-FredmanS #complexity #data type
- The Cell Probe Complexity of Dynamic Data Structures (MLF, MES), pp. 345–354.
- STOC-1987-BorodinLS #algorithm #online
- An Optimal Online Algorithm for Metrical Task Systems (AB, NL, MES), pp. 373–382.
- STOC-1987-LichtensteinLS #process #random
- Imperfect Random Sources and Discrete Controlled Processes (DL, NL, MES), pp. 169–177.
- STOC-1984-KahnS #comparison
- Every Poset Has a Good Comparison (JK, MES), pp. 299–301.