"1
`
`V
`
`U
`
`I
`
`°"‘UT-“”“°'“.Y 0*
`I»"‘cErp:z:5;5'Iiu.
`,2‘-°°°.I°“‘."!s of the
`»Th“§?1«ncM’5Ylposiun
`99”? Of Computing
`3§E*§$;cks
`Diego,
`
`Received’o,.
`
`PROCEEDINGS OF THE TWENTY—N|NTH
`
`ANNUAL ACM SYMPOSIUM ON
`
`THEORY OF COMPUTING
`
`
`
`El Paso, Texas
`
`May 4-6, 1997
`
`SPONSORED BY
`
`THE ACM SPECIAL INTEREST GROUP FOR
`
`ALGORITHMS AND COMPUTATION THEORY
`
`iii
`111
`
`Apple 1008
`Apple 1008
`
`

`
`The Assnciatimi for Computing Machinery
`1515 Broa(lwa_\'
`New York New York 10036
`
`Copyright 1997 by the Association for Computing Machinery. lnc.(ACM). Permission to
`make digital or hard work for personal or classroom use is granted without fee provided that
`the copies are not made or distributed for profit or commercial advantage and that copies
`bear this notice and the full citation on the first page. Copyrights for components of this
`
`work owned by others than ACM must be honored. Abstracting, with credit is permitted. To
`copy otherwise. to republish. to post on servers or to redistribute to lists requires prior
`specific permission and/or a fee. Request permission to republish from: Publications Dept.
`ACM, Inc. Fax +1 (2 I2) 869-0-181 or <permissions((11acm.org> For other copying of articles
`that. carry a code at the bottom of the lirst or last page. Copying is permitted provided that the
`per-copy fee indicated in the code is paid through the Cop_vright Clearance Center, 222
`Rosewood Drive. Danvers. MA 0 I923.
`
`ACM ISBN: 0-897‘) l -8884;
`
`Additional copies may be ordered prepaid from:
`
`ACM Order Department
`PO Box l2l 14
`Church Street Station
`
`ACM European Service Center
`108 Cowley Road
`Oxford OX 4
`1 JF
`
`New York, NY l0257
`
`-
`
`UK
`
`Phone: 1-800-342-()(i26
`
`(US and Canada)
`+1-212-626-0500
`(all other countries)
`Fax: +l—2l2-944-l 3 18
`
`E-mail: aeitipiibs((rlaeii1.oi'g
`
`Phone: +44-l-X()5-382338
`
`+44-l—865—38 I 338
`Fax:
`E-Mail: acm_europe/(ilacinorg
`URL:http1//www.acmorg
`
`ACM Order Number: 508‘)7(i)
`
`Printed in the USA
`
`iv
`
`iv
`
`

`
`Proceedings of the Twenty-Ninth Annual
`
`ACM Symposium on Theory of Computing
`
`May 4 — 6, 1997, El Paso, Texas
`
`TABLE OF CONTENTS
`
`Sunday, May 4
`
`Session 1A
`
`Some Optimal lnapproximability Results .
`Johan Hdstad
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`1
`
`A Complete Classification of the Approximability of Maximization Problems Derived from Boolean
`Constraint Satisfaction .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`Sanjeev Khanna, Madhu Sudan and David P. Williamson
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 11
`
`.
`
`. 21
`
`When Hamming Meets Euclid: The Approximability of Geometric TSP and MST .
`Luca Trevisan
`'
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session 1B
`
`Approximate Complex Polynomial Evaluation in Near Constant Work per Point
`John H. Reif
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Fast and Precise Computations of Discrete Fourier Transforms Using Cyclotomic Integers .
`Joe Buhler, M. Amin Shokrollahi and Volker Stemann
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 30
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 40
`
`Quantum Computation of Fourier Transforms over Symmetric Groups .
`Robert Beals
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 48
`
`Session 2A
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 54
`
`.
`
`. 66
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`General Techniques for Comparing Unrooted Evolutionary Trees .
`Ming-Yang Kao, Tak-Wah Lam, Teresa M. Przytycka, Wing-Kin Sung and Hing-Fung Ting
`Tree Pattern Matching and Subset Matching in Randomized 0(n1og3 m) Time .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Richard Cole and Ramesh Hariharan
`
`.
`
`.
`
`.
`
`.
`
`Session 2B
`
`Randomized Q(n2) Lower Bound for Knapsack .
`Dima Grigoriev and Marek Karpinski
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 76
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 86
`
`.
`.
`.
`.
`.
`.
`Exponential Lower Bounds for Depth 3 Boolean Circuits .
`Ramamohan Paturi, Michael E. Saks and Francis Zane
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Invited Session I
`
`Algorithmic Complexity in Coding Theory and the Minimum Distance Problem .
`Alexander Vardy
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 92
`
`Session 3A
`
`Approximating Total Flow Time on Parallel Machines .
`Stefano Leonardi and Danny Raz
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 110
`
`Non—Clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics .
`JeffEdmonds, Donald D. Chinn, Tim Brecht and Xiaotie Deng
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 120
`
`

`
`Better Bounds for Oniine Scheduling .
`Susanne Albers
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 130
`
`. 140
`
`.
`.
`.
`Optimal Time—Critical Scheduling via Resource Augmentation .
`Cynthia A. Phillips, Clifl Stein, Eric Torng and Joel Wein
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session 3B
`
`Practical L0ss—Resilient Codes .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 150
`
`Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, Daniel A. Spielman and
`Volker Stemann
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 160
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Spectral Techniques for Expander Codes .
`John D. Lajferty and Daniel N. Rockmore
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Faster Solution of the Key Equation for Decoding BCH Error—Correcting Codes .
`Victor X Pan
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 168
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 176
`
`Fault Tolerant Quantum Computation with Constant Error .
`Dorit Aharonov and Michael Ben-Or
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session 4A
`
`On the Construction of Pseud0—Rand0m Permutations: Luby—Rack0ff Revisited .
`Moni Naor and Omer Reingold
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 189
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 200
`
`Reducing Randomness via Irrational Numbers .
`Zhi-Zhong Chen and Ming-Yang Kao
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Is There an Algebraic Proof for P 75 NC? .
`Ketan Mulmuley
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 210
`
`. 220
`
`P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma .
`Russell Impagliazzo and Avi Wigderson
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`SL c L% ..................................................................................... .. 230
`
`Ray Armani, Amnon Ta-Shma, Avi Wigderson and Shiyu Zhou
`
`Session 4B
`
`Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs .
`David Karger
`
`.
`
`Combinatorial Complexity of the Central Curve .
`Peter A. Beling and Sushil Verma
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 240
`
`.
`
`. 250
`
`.
`
`. 256
`
`Approximation of k-Set Cover by Semi-Local Optimization .
`Rong-chii Duh and Martin Fiirer
`
`.
`
`.
`
`Approximation Algorithms for Facility Location Problems .
`David B. Shmoys, Eva Tardos and Karen Aardal
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 265
`
`Covering Points in the Plane by k—Tours: Towards a Polynomial Time Approximation Scheme for
`General is .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. .. 275
`
`Tetsuo Asano, Naoki Katoh, Hisao Tamaki and Takeshi Tokuyama
`
`Monday, May 5
`
`Session SA
`
`A Public—Key Cryptosystem with Worst—Case/Average‘—Case Equivalence .
`Miklés Ajtai and Cynthia Dwork
`‘
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 284
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Private Information Storage .
`Rafail Ostrovsky and Victor Shoup
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 294
`
`vi
`
`

`
`Computationally Private Information Retrieval .
`Benny Chor and My Gilboa
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 304
`
`Session 5B
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 314
`
`Approximating Hyper—Rectangles: Learning and Pseudo—Random Sets .
`Peter Auer, Philip M. Long and Aravind Srinivasan
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes .
`Shai Ben—David, Nader H. Bshouty and Eyal Kushilevitz
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Using and Combining Predictors that Specialize .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Yoav Freund, Robert E. Schapire, Yoram Singer and Manfred K. Warmuth
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 324
`
`.
`
`.
`
`.
`
`.
`
`. 334
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session 6A
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 344
`
`On-Line Algorithms for Steiner Tree Problems .
`Piotr Berman and Chris Coulston
`
`.
`
`,
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Online Algorithms for Selective Multicast and Maximal Dense Trees .
`Baruch Awerbuch and Tripurari Singh
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 354
`
`Session 6B
`
`Direct Product Results and the GCD Problem, in Old and New Communication Models .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 363
`
`Itzhak Parnafes, Ran Raz and Avi Wigderson
`
`.
`
`.
`
`.
`
`. 373
`
`The Linear-Array Problem in Communication Complexity Resolved .
`Martin Dietzfelbinger
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Invited Session II
`
`Paul Erd6's (1913-1996): His Influence on the Theory of Computing .
`Ldszlo’ Babai
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 383
`
`Session 7A
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 402
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Permanents, Pfaffian Orientations, and Even Directed Circuits .
`William McCuaig, Neil Robertson, P. D. Seymour and Robin Thomas
`Property Testing in Bounded Degree Graphs .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`,
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Oded Goldreich and Dana Ron
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 406
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 416
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Exploring Unknown Environments .
`Susanne Albers and Monika R. Henzinger
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 426
`
`On Floorplans of Planar Graphs .
`Xin He
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session 7B
`
`Linear Zero-Knowledge — A Note on Efficient Zero-Knowledge Proofs and Arguments .
`Ronald Cramer and Ivan Damgard
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 436
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 446
`
`Commodity—Based Cryptography .
`Donald Beaver
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Oblivious Data Structures: Applications to Cryptography .
`Daniele Micciancio
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 456
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Is Linear Hashing Good? .
`Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank and Gdbor Tardos
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 465
`
`vii
`
`

`
`Session 8A
`
`A Sub—Const_ant Error—Probability Low-Degree Test, and a Sub—Constant Error—Probability PCP
`Characterization of NP .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`Ran Raz and Shmuel Safra
`
`Improved Low Degree Testing and its Applications .
`Sanjeev Arora and Madhu Sudan
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 475
`
`. 485
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 496
`
`Probabilistically Checkable Proofs with Zero Knowledge .
`Joe Kilian, Erez Petrank and Gdbor Tardos
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`,
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 506
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Making Games Short .
`Uriel Feige and Joe Kilian
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`,
`
`.
`
`Session 8B
`
`Improved Routing and Sorting on Multibutterflies .
`Bruce M. Maggs and Berthold Vdcking
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 517
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 531
`
`Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach .
`Andrei Z. Broder; Alan M. Frieze and Eli Upfal
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`On Sorting Strings in External Memory .
`Lars Arge, Paolo Ferragina, Roberto Grorsi and Jeffrey Scott Vitter
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 540
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 549
`
`Pointer Jumping Requires Concurrent Read .
`Noam Nisan and Ziv Bar- Yossef
`
`.
`
`.
`
`.
`
`Tuesday, May 6
`
`Session 9A
`
`Lower Bounds for Distributed Coin-Flipping and Randomized Consensus .
`James Aspnes
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 559
`
`. 569
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Byzantine Quorum Systems .
`Dahlia Malkhi and Michael Reiter
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`All of Us Are Smarter Than Any of Us: Wait—Free Hierarchies Are Not Robust .
`Wai-Kau Lo and Vassos Hadzilacos
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 579
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 589
`
`The Decidability of Distributed Decision Tasks .
`Maurice Herlihy and Sergio Rajsbaum
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session 9B
`
`Two Algorithms for Nearest—Neighbor Search in High Dimensions .
`Jon M. Kleinberg
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 599
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 609
`
`Nearest Neighbor Queries in Metric Spaces .
`Kenneth L. Clarkson
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Locality-Preserving Hashing in Multidimensional Spaces .
`Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan and Santosh Vempala
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 618
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Incremental Clustering and Dynamic Information Retrieval .
`Moses Charikar, Chandra Chekuri, Tomas Feder and Rajeev Motwani
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 626
`
`Session 10A
`
`A Constant—Factor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global
`Criteria .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 636
`
`Aravind Srinivasan and Chung-Piaw Teo
`
`viii
`
`

`
`Universal O(congestion+dilation+log1+‘N) Local Control Packet Switching Algorithms .
`Rafail Ostrovsky and Yuval Rabani
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 644
`
`Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the
`World Wide Web .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`. 654
`
`David Karger; Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin and
`Rina Panigrahy
`
`.
`.
`.
`.
`.
`.
`.
`Allocating Bandwidth for Bursty Connections .
`Jon Kleinberg, Yuval Rabani and Eva Tardos
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 664
`
`Session 10B
`
`.
`
`.
`
`.
`
`. 674
`
`The Swendsen—Wang Process Does Not Always Mix Rapidly .
`Vivek K. Gore and Mark R. Jerrum
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 682
`
`.
`.
`.
`Approximately Counting up to Four .
`Michael Luby and Eric Vigoda
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`An Interruptible Algorithm for Perfect Sampling via Markov Chains .
`James Allen Fill
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 688
`
`. 696
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Sampling Lattice Points .
`Ravi Kannan and Santosh Vempala
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session 11A
`
`Page Replacement with Multi-Size Pages and Applications to Web Caching .
`Sandy Iram‘
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 701
`
`. 711
`
`.
`.
`A Polylog(n)—Competitive Algorithm for Metrical Task Systems .
`Yair Bartal, Avrim Blum, Carl Burch and Andrew Tomkins
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session 11B
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 720
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`On ACC°[ pk] Frege Proofs .
`Alexis Maciel and Toniann Pitassi
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Reducing the Complexity of Reductions .
`Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi and Steven Rudich
`
`.
`
`.
`
`.
`
`. 730
`
`Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal
`Calculus .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`. 739
`
`Alexander Razborov, Avi Wigderson and Andrew Yao
`
`Errata
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 749
`
`Eigenvalues, Flows and Separators of Graphs .
`F R. K. Chung and S.—T. Yau
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Retraction of “Probabilistic Computation and Linear Time” .
`Lance Fortnow and Michael Sipser
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 750
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 751
`
`Author Index .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`ix
`
`

`
`Practical Loss-Resilient Codes
`
`Michael G. Luby"‘
`
`Michael Mitzenmacherl
`
`M. Arnin Shokrollahii
`
`Daniel A. Spielman-§
`
`Volker Stemannl
`
`Abstract
`
`We present randomized constructions of linear-time en-
`codable and decodable codes that can transmit over lossy
`channels at rates extremely close to capacity. The encod-
`ing and decoding algorithms for these codes have fast and
`simple software implementations. Partial implementations
`of our algorithms are faster by orders of magnitude than the
`best software implementations of any previous algorithm for
`this problem. We expect these codes will be extremely useful
`for applications such as real—time audio and video transrnis—
`sion over the Internet. where lossy channels are common and
`fast decoding is a requirement.
`Despite the simplicity of the algorithms, their design and
`analysis are mathematically intricate. The design requires the
`careful choice of a random irregular bipartite graph, where
`the structure of the irregular graph is extremely important.
`We model the progress of the decoding algorithm by a set
`of differential equations. The solution to these equations can
`then be expressed as polynomials in one variable with coef-
`
`‘Digital Equipment Corporation, Systems Research Center, Palo Alto,
`CA, and Computer Science Division, University ofCalifornia at Berkeley. A
`substantial portion of this research done while at the International Computer
`Science Institute. Research supported in part by National Science Founda-
`tion operating grant NCR—9416l0l,and United States-Israel Binational Sci-
`ence Foundation grant No. 92-00226.
`lDigital Equipment Corporation, Systems Research Center, Palo Alto,
`CA. A substantial portion of this research done while at the Computer Sci-
`ence Department, UC Berkeley, under the National Science Foundation
`grant No. CCR-9505448.
`Untemational Computer Science Institute Berkeley, and lnstitut fur In-
`formatik der Universitat Bonn, Gemiany. Research supported by a Habilita-
`tionsstipendium ofthe Deutsche Forschungsgemeinschaft, Grant Sh 57/ l—l .
`§Department of Mathematics, M.I.T. Supported by an NSF mathematical
`sciences postdoc. A substantial portion of this research done while visiting
`U.C. Berkeley.
`‘Research done while at the International Computer Science Institute
`
`l’I.!l'llll.\‘.\‘i0ll to ninkc digital/|i:ii'd copies olull or part nl'l|iis nmlcrizil Ihr
`personal or Cll|.\‘.\'l‘00Ill us»: is grunlcrl without lbc pm\'ide<l that lhc copies
`are not inmlc or dislrihulctl for prolil or cumin-:i'ci:il ;itl\':inl:igc. the copy-
`riglil nnli-:e. lhc lilli.‘ olilhc puliliculion and ils dzilc zippczir. and notice is
`given that copyi'ig|iI is by pcmiission oflhc .~'\Cl\l. Inc. To copy ollicrwisc.
`to repulilisli. to post on servers or to i'edislribiilc lo lists. l‘L‘l]llll'l.‘.\' spccilic
`pennissiun sinilni‘ let‘
`S''/'()(' ")7 lil
`|‘:iso. 'l'c.\.'1s l ‘S.-\
`Copyriglit l‘)‘)7 .-\L‘.\-l I)-X07‘)l-XXX-6/‘)7.=0S ...\I‘.l.5()
`
`ficients determined by the graph structure. Based on these
`polynomials, we design a graph structure that guarantees suc-
`cessful decoding with high probability.
`
`1
`
`Introduction
`
`Studies show that the Internet exhibits packet loss, and
`the measurements in [10] show that the situation has become
`worse over the past few years. A standard solution to this
`problem is to request retransmission of data that is not re-
`ceived. When some of this retransmission is lost, another re-
`
`In some applications, this intro-
`quest is made, and so on.
`duces technical difficulties. For real-time transmission this
`
`solution can lead to unacceptable delays caused by several
`rounds of communication between sender and receiver. For
`
`a multicast protocol with one sender and many receivers, dif-
`ferent sets of receivers can lose different sets of packets, and
`this solution can add significant overhead to the protocol.
`An alternative solution, often called forward error-
`correction in the networking literature,
`is sometimes
`desirable. Consider an application that sends a real-time
`stream of data symbols that is partitioned and transmitted in
`logical units of blocks.‘ Suppose the network experiences
`transient and unpredictable losses of at most a p fraction of
`symbols out of each block. The following insurance policy
`can be used to tradeoff the effects of such uncontrollable
`
`losses on the receiver for controllable degradation in quality.
`Let n be the block length.
`Instead of sending blocks of n
`data symbols each, place (1 — p)n data symbols in each
`block, by either selecting the most important parts from
`the original data stream and omitting the remainder, or
`by generating a slightly lower quality stream at a (1 — p)
`fraction of the original rate. Fill out the block to its original
`length of n with pn redundant (check) symbols. This scheme
`provides optimal loss protection if the (1 —— p)n symbols in
`the message can all be recovered from any set of (1 — p)n
`
`‘An example of this is an MPEG stream, where a group ofpictures can
`constitute such a block. and where each symbol corresponds to the contents
`of one packet in the block. The latency incurred by the application is propor-
`tional to the time it takes between when the first and last packet of the block
`is sent, plus the one-way travel time through me network.
`
`

`
`received symbols from the block. Such a scheme can be
`used as the basic building block for the more robust and
`general protection scheme described in [1].
`To demonstrate the benefits of forward error—correction in
`
`a simplified setting, consider the Internet loss measurements
`perfonned by [14] involving a multicast by one sender to a
`number of geographically distributed receivers. In one typi-
`cal transmission to eleven receivers for a period of an hour,
`the average packet loss rate per receiver was 9.3%, yet 46.5%
`of the packets were lost by at least one of the receivers. To
`simplify the example, suppose that the maximum loss rate
`per block of 1000 packets for any receiver is 200.2 Then, the
`sender could use forward error—correction by adding 200 re-
`dundant packets to each 800 data packets to form blocks con-
`sisting of 100 packets each. This approach sends 25% more
`packets total than are in the original data stream, whereas
`a naive scheme where the sender retransmits lost packets
`would send about 50% more.
`
`It is a challenge to design fast enough encoding and de-
`coding algorithms to make forward error—correction feasible
`in real-time for high bandwidth applications. In this paper,
`we present codes that can be encoded and decoded in linear
`time while providing near optimal loss protection. Moreover.
`these linear time algorithms can be implemented to run very
`quickly in software.
`Our results hold whether each symbol is a single bit or a
`packet of many bits. We assume that the receiver knows the
`position of each received symbol within the stream of all en-
`coding symbols. This is appropriate for the Internet, where
`packets are indexed. We adopt as our model of losses the era-
`sure channel, introduced by Elias [6], in which each encod-
`ing symbol is lost with a fixed constant probability p in transit
`independent of all the other symbols. This assumption is not
`appropriate for the Internet, where losses can be highly cor-
`related and bursty. However, losses on the Internet in general
`are not sensitive to the actual contents of each packet, and
`thus if we place the encoding into the packets in a random
`order then the independent loss assumption is valid.
`Elias [6] showed that the capacity of the erasure channel
`is 1 — p and that a random linear code can be used to trans-
`mit over the erasure channel at any rate R < 1 — p. Fur-
`thermore, a standard linear MDS code can be used to con-
`vert a message of length Rn into a transmission of length n
`from which the message can be recovered from any portion of
`length greater than Rn. Moreover, general linear codes have
`quadratic time encoding algorithms and cubic time decoding
`algorithms. One cannot hope for better information recovery,
`but faster encoding and decoding times are desirable, espe-
`cially for real-time applications.
`Reed-Solomon codes can be used to transmit at the ca-
`
`pacity of the erasure channel with n log n encoding time
`and quadratic decoding time. These codes have recently
`
`2This is twice the average loss rate, but due to the bursty nature of losses
`in the lntemet it is still likely that the maximum loss rate per block exceeds
`20%. One can use the results of [ l] to simultaneously protect against various
`levels of loss while still keeping the overall redundancy modest.
`
`been customized to compensate for Internet packet loss in
`real-time transmission of moderate-quality video [1]. Even
`this optimized implementation required the use of dedicated
`workstations. Transmission of significantly higher quality
`video requires faster coding algorithms.
`
`In theory, it is possible to decode Reed-Solomon codes
`in time (9(nlog2nlog log 11) (see,
`[4, Chapter 11.7] and
`[9, p. 369]). However, for small values of n, quadratic
`time algorithms are faster than the fast algorithms for the
`Reed-Solomon based codes, and for larger values of n the
`O(log2 n log log n) multiplicative overhead in the running
`time of the fast algorithms (with a moderate sized constant
`hidden by the big-Oh notation) is large, i.e., in the hundreds
`or larger.
`
`We obtain very fast linear-time algorithms by transmitting
`just below channel capacity. We produce rate R = 1 — p(1+
`6) codes along with decoding algorithms that recover from
`the random loss of a p fraction of the transmitted symbols in
`time proportional to n ln(1/5) with high probability, where
`n is the length of the encoding. They can also be encoded in
`time proportional to n II1(1/6). In Section 7, we do this for all
`6 > 0. The fastest previously known encoding and decoding
`algorithms [2] with such a performance guarantee have run
`times proportional to nlI1(1/6)/6. (See also [3] for related
`work.)
`The overall structure of our codes are related to codes in-
`
`troduced in [13] for error—correction. We explain the gen-
`eral construction along with the encoding and decoding al-
`gorithms in Section 2.
`
`Our encoding and decoding algorithms are almost sym-
`metrical. Both are extremely simple, computing exactly one
`exclusive-or operation for each edge in a randomly chosen bi-
`partite graph. As in many similar applications, the graph is
`chosen to be sparse, which immediately implies that the en-
`coding and decoding algorithms are fast. Unlike many sim-
`ilar applications, the graph is not regular; instead it is quite
`irregular with a carefully chosen degree sequence. We de-
`scribe the decoding algorithm as a process on the graph in
`Section 3. Our main tool is a model that characterizes almost
`
`exactly the performance of the decoding algorithm as a fimc-
`tion of the degree sequence of the graph. In Section 4, we use
`this tool to model the progress of the decoding algorithm by
`a set of differential equations. As shown in Lemma 1, the so-
`lution to these equations can then be expressed as polynomi-
`als in one variable with coefficients determined by the degree
`sequence. The positivity of one of these polynomials on the
`interval (0, 1] with respect to a parameter 6 guarantees that,
`with high probability, the decoding algorithm can recover al-
`most all the message symbols from a loss of up to a 6 frac-
`tion of the encoding symbols. The complete success of the
`decoding algorithm can then be demonstrated by combinato-
`rial arguments such as Lemma 3.
`
`Our analytical tools allow us to almost exactly charac-
`terize the performance of the decoding algorithm for any
`given degree sequence. Using these tools, we analyze reg-
`
`

`
`ular graphs in Section 6, and conclude that they cannot yield
`codes that are close to optimal. Hence irregular graphs are a
`necessary component of our design.
`
`Not only do our tools allow us to analyze a given degree
`sequence, but they also help us to design good irregular de-
`gree sequences. In Section 7 we describe, given a parameter
`c > O, a degree sequence for which the decoding is success-
`ful with high probability for a loss fraction 6 that is within 5 of
`l — R. Although these graphs are irregular, with some nodes
`of degree 1 /c, the average node degree is only ln(1/6). This
`i