6 papers:
ICALP-1998-PelegR #approximate #communication- Deterministic Polylog Approximation for Minimum Communication Spanning Trees (DP, ER), pp. 670–681.
STOC-1997-BartalBBT #algorithm- A polylog(n)-Competitive Algorithm for Metrical Task Systems (YB, AB, CB, AT), pp. 711–719.
- STOC-1995-Pan #algorithm #approximate #parallel #polynomial
- Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros (VYP), pp. 741–750.
- STOC-1995-SaksSZ
- Explicit dispersers with polylog degree (MES, AS, SZ), pp. 479–488.
- STOC-1994-Cohen #approximate
- Polylog-time and near-linear work approximation scheme for undirected shortest paths (EC), pp. 16–26.
- STOC-1992-Beigel
- When Do Extra Majority Gates Help? Polylog(n) Majority Gates Are Equivalent to One (RB), pp. 450–454.
