KRCM S‘
`.
`.‘CaIP‘-»'§::;S'iu. an vTbe°'77 °f
`Proceedings of the ..
`
`PROCEEDINGS OF THE TWENTY-NINTH
`
`ANNUAL ACM SYMPOSIUM ON
`
`THEORY OF COMPUTING
`
`r
`
`I
`
`//
`
`_...II
`
`
`
`El Paso, Texas
`
`May 4-6, 1997'
`
`SPONSORED BY
`
`THE ACM SPECIAL INTEREST GROUP FOR
`
`ALGORITHMS AND COMPUTATION THEORY
`
`Apple 1108
`
`Apple 1108
`
`

`
`The Association for Cuinpulingg M:u'|1inory
`1515 Bro:Itlwn_\'
`New York New York lt|t|3(i
`
`Copyrigltl 19‘)? by the Association for Computing, Ma1chiner_\-'_ inc.(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 commerci:-II :-tdv:-u1t:tgc and that copies
`bear this notice nud the full citation on the first page. Cop_x'rig,hts 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 tuidior a fee. Request permission to republish from: Publications Dept.
`ACM, Inc. Fax +1 (212) Sm)-£1481 or <permissioiis(rr1;IcIu.org> For other copying of articles
`that e:-trry 21 code at the bottom oflhe lirst or last page. C0])_\'i]Ig is permitted provided that the
`per-copy fee indicated in the code is paid throng.-,h the Copyrigltt Clearance Center, 222
`Rosewood Drive. Dam-'ers_ MA ttIl)2_"i.
`
`ACM ISBN: ll-X97‘) I —XKX—(i
`
`Additional copies m:]_\' be ordered prepaid from:
`
`ACM Order Department
`PO Box 12! I4
`Church Street Station
`New York, NY l{t2:'17
`
`Phone:
`
`l—Xt]0-342-6626
`
`(US and Cillltldil)
`+1-212-626-Ofitttl
`(all other countries)
`Fax: +l—2l2~9-‘I-I-I 3 13
`
`E-mail: ac:rtpitbs{ri1aei1i.oI'g
`
`-
`
`ACM European Service Center
`NIX Cowle_\= Road
`Oxford OX 4 I JF
`UK
`
`Phone: +-1-1-I-865-382338
`
`+44-I-865-381333
`Fox:
`E~MaiI: ;-1cin_eui‘o:Je-’(il2tci1i.org
`URL:ltttp:t'r‘\\-'\\'\\'.:1ctn_org
`
`ACM Order Number: 5{lR‘)7tt
`
`Printed in the USA
`
`

`
`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 IA
`
`Some Optimal Inapproximability Results .
`Johan Hdstad
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`1
`
`A Complete Classification of the Approximability of Maximization Problems Derived from Boolean
`Constraint Satisfaction .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`Sanjeev Khamza, Madhu Sudan and David R Williamson
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 11
`
`.
`
`. 21
`
`When Hamming Meets Euclid: The Approximability of Geometric TSP and MST .
`Luca Trevisan
`-
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session II!
`
`Approximate Complex Polynomial Evaluation in Near Constant Work per Point
`John H. Ralf
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Fast and Precise Computations of Discrete Fourier Transforms Using Cyclotomic Integers .
`Joe Buhter; M. Amin Shokrolfahi and Volker Sremann
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 30
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 40
`
`Quantum Computation of Fourier Transforms over Symmetric Groups .
`Robert Beafs
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 48
`
`Session 2A
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 54
`
`. 66
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`General Techniques for Comparing Unrooted Evolutionary Trees .
`Mi'ng—Yang Kao, Tak-Wah Lam, Teresa M. Przytycka, Wi'ng—Ki'n Sung and Hing-Fang Ting
`Tree Pattern Matching and Subset Matching in Randomized O(n log3 m) Time .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Richard Cole and Ramesh Hariharan
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session 2B
`
`Randomized Q('l"l.2) Lower Bound for Knapsack .
`Dima Grigoriev and Mare)‘: Karpinski
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 76
`
`. S6
`
`.
`.
`.
`.
`.
`.
`Exponential Lower Bounds for Depth 3 Boolean Circuits .
`Ramamohan Paruri. 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
`
`N on-Clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics .
`Jeff Edmonds, Donald D. Chinn, Tim Brecht and Xiaorie Deng
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 120
`
`

`
`Better Bounds for Online Scheduling .
`Susanne Aibers
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 130
`
`. 140
`
`.
`.
`.
`Optimal Timc—Critical Scheduling via Resource Augmentation .
`Cynthia A. Phillips, CliffStein, Eric Torng and Joel Weir:
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session 313
`
`Practical Loss-Resilient Codes .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 150
`
`Michael G. Liiby. Michael Mitzenmaclter, M. Amin Sholcmliahi, Daniel A. Spieiman and
`Volker Stemamt
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 160
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Spectral Techniques for Expander Codes .
`John D. Lafi”en:3= and Daniel N. Roe.-‘(more
`
`.
`
`. .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Faster Solution of the Key Equation for Decoding BCH Error-Correctin g Codes .
`Victor 1’. Pan
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`I68
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 176
`
`Fault Tolerant Quantum Computation with Constant Error .
`Dorit Altaron ov and Michael Ben-Or
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session 4A
`
`On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited .
`Mani Naor and Omer Reingold
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`I89
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 200
`
`Reducing Randomness via Irrational Numbers .
`Ziii-Zhong Chen and Ming—l"ang Karo
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`ls There an Algebraic Proof for P 75 NC? .
`Ketari Mulmuiey
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. .
`
`.
`
`.
`
`.
`
`.
`
`. .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 210
`
`. 220
`
`P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma .
`Russell Impagliazza and Avi Wigdermn
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`SL c L? ..................................................................................... .. 230
`
`Roy Annoni, Amnon Ta—Sizma, Avi Wigderson and Sliiyu Zlzou
`
`Session 4B
`
`Using Random Sampling to Find Maximum Flows in Uncapacitatcd Undirected Graphs .
`David Karger
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Combinatorial Complexity of the Central Curve .
`Peter A. Belling and Susltil Verma
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 240
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 250
`
`.
`
`.
`
`.
`
`.
`
`. 256
`
`Approximation of la-Set Cover by Semi—Local Optimization .
`Rong—ch ii Duh and Martin Fiirer
`
`Approximation Algorithms for Facility Location Problems .
`David B. Sltmoys, Eva Tardos and Karen Aardal
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. . .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 265
`
`Covering Points in the Plane by ls:-Tours: Towards a Polynomial Time Approximation Scheme for
`General if
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. .. 275
`
`Tetsuo Asano, Naoki Katoh, Hisao Tamaki and Takeshi Tokiiyama
`
`Monday, May 5
`
`Session SA
`
`. 284
`
`A Public-Key Cryptosystem with Worst—CaselAverage-Case Equivalence .
`Mikitis Ajtai and Cynthia Dworic
`'
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`.
`.
`.
`.
`. .
`.
`.
`.
`.
`.
`.
`.
`Private Information Storage .
`Rafail Ostrovsky and Victor Slioiip
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 294
`
`vi
`
`

`
`Computationally Private Information Retrieval
`Benny Char and Niv Gilboa
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 304
`
`Session SB
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 314
`
`Approximating Hyper-Rectangles: Learning and Pseudo—Random Sets .
`Peter Auet; Philip M. Long and Aravind Srinivasan
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes .
`Shai Ben—David, Nader H. Bshonty and Eyal Kushilevirz
`
`.
`
`.
`
`.
`
`. 324
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Using and Combining Predictors that Specialize .
`Yoav Freund, Robert‘ E. Scnapire, Yarant Singer and Manfred K. Wannnrn
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 334
`
`Session 6A
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 344
`
`On-Line Algorithms for Steiner Tree Problems .
`Piotr Berman and Chris Coulsron
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Online Algorithms for Selective Multicast and Maximal Dense Trees .
`Baruch Awerbnch and Tripurari Singh
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 354
`
`Session 6B
`
`Direct Product Results and the GCD Problem, in Old and New Communication Models .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 363
`
`Itzhalc Parnafes, Ran Raz and Aw‘ Wigderson
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 373
`
`The Linear-Array Problem in Communication Complexity Resolved .
`Martin Dietzfelbinger
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Invited Session II
`
`Paul Erdfis (1913-1996): His Influence on the Theory of Computing .
`Laszlo Babai
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 383
`
`Session TA
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 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 TB
`
`Linear Zero-Knowledge — A Note on Efficient Zero—Knowledge Proofs and Arguments .
`Ronald Cramer and [van Damgcird
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 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 Milrersen, Erez Petrank and Gcibar Tardos
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 465
`
`vii
`
`

`
`Session SA
`
`A Sub-Constant Error-Probability Low-Degree Test, and a St1b—Constant Error-Probability PCP
`Characterization of NP .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`Ran Roz and Shmuei Safra
`
`Improved Low Degree Testing and its Applications .
`Sanjeev Arora and Madhu Sudan
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 475
`
`. 485
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. . .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 496
`
`Probabiiistically Checkable Proofs with Zero Knowledge . . .
`Joe Kilian, Erez Petrank and Gribor Tardos
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 506
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Making Games Short .
`Uriel Feige and Joe Kilian
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session SB
`
`Improved Routing and Sorting on Multibutterflies .
`Bruce M. Maggs and Berthold Vocking
`
`.
`
`.
`
`.
`
`. .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. . .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 517
`
`Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach .
`Andrei Z. Broder; Alan M. Frieze and Eii Upfai
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 531
`
`.
`
`.
`
`. S40
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`On Sorting Strings in External Memory .
`Lars Arge, Panto Ferragina, Roberto Grossi and Jefi"rey Scan‘ ‘Virter
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 549
`
`Pointer Jumping Requires Concurrent Read .
`Noam Nixon 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 Maikhi and Michaei Reiter
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`All of Us Are Smarter Than Any of Us: Wait—Frce Hierarchies Are Not Robust .
`Wai-Kan Lo and Vassos Hadziiacos
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 579
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. . .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 589
`
`The Decidability of Distributed Decision Tasks .
`Maurice Heriihy and Sergio Rajsbaum
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session 9B
`
`Two Algorithms for Nearest-Neighbor Search in High Dimensions .
`Jon M. Kieinberg
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 599
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 609
`
`Nearest Neighbor Queries in Metric Spaces .
`Kenneth L. Ciarkson
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Locality—Preserving Hashing in Multidimensional Spaces .
`Piotr Indyk, Rajeev Morwani, Prabhakar Raghavan and Sanrosh ‘I/empaia
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 618
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Incremental Clustering and Dynamic Information Retrieval .
`Moses Charikar; Chandra Chekuri, Tomcis Feder and Rajeev Morwani
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 626
`
`Session 10A
`
`A Constant—Faetor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global
`Criteria .
`.
`.
`.
`.
`.
`.
`.
`. .
`.
`. . .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 636
`
`Aravind Srinivasan and Chung-Piaw Tea
`
`viii
`
`

`
`Universal O(congestion+dilation+log1+‘N) Local Control Packet Switching Algorithms .
`Rafaii Osrnavsky and Yuvai Rabani
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 644
`
`Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the
`World Wide Web .
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`. 654
`
`David Kargei; Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin and
`Rina Panigrahy
`
`.
`.
`.
`.
`.
`.
`.
`Allocating Bandwidth for Bursty Connections .
`Jon Kieinberg. Yuvai 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 .
`Michaei Luby and Eric Vigoda
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`An Interruptible Algorithm for Perfect Sampling via Markov Chains .
`James Alien Fifi
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 688
`
`.
`
`.
`
`.
`
`. 696
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Sampling Lattice Points .
`Ravi Kannan and Santosh Vempala
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`Session 11A
`
`Page Replacement with Multi-Size Pages and Applications to Web Caching .
`Sandy Irani
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 701
`
`.
`.
`A Polylog(n)—Con1petitive Algorithm for Metrical Task Systems .
`Yair Barrel, Avrim Bium, Cari Burch and Andrew Tomkins
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 711
`
`Session 11B
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 720
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`On ACC0[p’°] Frege Proofs .
`Aiexis Maciei and Toniann Pitassi
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`Reducing the Complexity of Reductions .
`Manindra Agrawal, Eric Aiiender; Russel! Impagiiazzo, Toniarm Pirassi and Steven Rudich
`
`.
`
`.
`
`.
`
`. T-"30
`
`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 Forrnow and Michaei Sipser
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 1'50
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. 751
`
`Author Index .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`. .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`

`
`Practical Loss-Resilient Codes
`
`Michael G. Luby"
`
`Michael Nfitzenmacheri
`
`M. Amin Shokrollahii
`
`Daniel A. Spielman§
`
`Volker Stemann‘
`
`Abstract
`
`We present randomized constructions of linear-time en-
`codable and decodabie 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 transmis-
`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 ofCaliforniaat 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-94 16 I01 .and United States-Israel Binational Sci-
`ence Foundation grant No. 92-00226.
`1 Digital 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.
`‘International Computer Science Institute Berkeley. and lnstitut liir In-
`formatik der Universitlit Bonn, Germany. Research supported by a Habitua-
`tionsstipendiurn of the Deutsche Foischungsgemeinschafi, Grant Sh 572'I—l.
`5Department of Mathematics, M.l.T. Supponed by an NSF mathematical
`sciences postdoc. A substantial portion of this research done while visiting
`U.C. Berkeley.
`‘Research done while at the lntcmaiional Computer Science Institute
`
`l’L‘I'I1li!o&iim to mnitc tligi[.'tl.’|'t:i:'ti t'upit:.-: r‘ii':.|II nrp:i11 nI'lhi.\' n1;i1t:n;|l Iiir
`pelsonatl or cl;|_~t~'rm1nl IISL.‘ is 1.-,|‘:|IIli:il with-iul fut‘ pru\‘iu.lc:l that Iln: mpic.-a
`are not II'|:l(lL‘ or tll.'<|l'll'ItlIt‘ll l1\|'proIiI or t‘oItnnn.‘I'L‘i:Il ad\':IiiI;|gt‘. the copy.
`right notice. the title oftllc |"|l.ll\llI.I«'IllUIl and il.\: tl.'IlL' :t|Ipu:.'u'. and nnlici: is
`given ll1:It t‘t>p)'rip_|tl is h_\‘ pclinixximl olilhi.‘ .=\Cl\'l. Int‘. Toi.'i1]1}'nl|lcn\'i$c.
`to rcptililisli. to p0.~'I on :<t‘|'\'t:ix or to rciii.-:lribiIlc Io Iisls. '.|‘l.‘l|llil'I.‘.\' spccilic
`pL'l'llll>'¢litIt'l :IIltl-Ill‘ r.~.~
`.'§'i"f)i" “J7 I-ll
`|‘.'i.sn.'|'c.\:I.<:|‘.‘i:\
`Copyriglll I9-J7 .-\t'.\I ll-K‘J}"J l—8t<x—t.i9'l.-t::’~ .
`
`:'.s'.1.fiu
`
`ficients dctennined 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 [I0] 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 elfects of such uncontrollable
`
`losses on the receiver for controllable degradation in quality.
`Let n be the block length. Instead of sending blocks of it
`data symbols each, place (1 — 39):: 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 pa redundant (check) symbols. This scheme
`provides optimal loss protection if the (1 - 39):: 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 gmirp ofpictures can
`constitute such a block, and where each symbol corresponds to the contents
`of one packet in the block. 1112 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 the network.
`
`

`
`receivcd 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 [I].
`To demonstrate the benefits of forward error—correction in
`
`a simplified setting, consider the Internet loss measurements
`performed by [14] involvinga 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 fonn 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 hits. 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 em-
`snre channel. introduced by Elias [6], in which each encod-
`ing symbol is lost with a fixed constant probability pin 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-
`thennore, 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 berecovered 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 rt encoding time
`and quadratic decoding time. These codes have recently
`
`3This is twice the average loss rate, but due to the bursty nature of losses
`in the Internet it is still likely that the maximum loss rate per block exceeds
`20%. One can use the results of [I] to silnultuneously pmtectaguinst 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 O(nlog2nloglog n) (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 T3 the
`O{log2 rrlog 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+
`5] 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 r1ln(1/6). In Section 7, we do this for all
`e > 0. The fastest previously known encoding and decoding
`algorithms [2] with such a perfonnance guarantee have run
`times proportional to n ln(1/c){e. (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-oroperation 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 func-
`tion of the degree sequence of the graph. In Section 4, we use
`this tool to model the progress of the decoding algorithm by
`it 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-
`
`

`
`computes the sum
`modulo 2 of its
`neighbors
`
`(:11) A graph defines a mapping from message bits
`Figure 1:
`to check hits.
`
`(it) Bits :1. £3, and c; are used to solve for :23.
`
`Decoding Operation
`
`Given the value of a check bit and all but one of
`
`the message bits on which it depends,
`set the missing momage bit to be the G) of the
`check bit and its known message hits.
`
`See Figure 1(6) for an example of