`
`
`
`.mnwwm'un',.1:3firuflirme‘v.v”.-v,w
`
`ALGORITHMS AND ..
`
`THEORY
`
`
`Hughes,EXh.fb{5;p.1
`
`Hughes, Exh. 1015, p. 1
`
`

`

`PROCEEDINGS OF THE THIRTIETH
`
`ANNUAL ACM SYMPOSIUM ON
`
`THEORY OF COMPUTING
`
`Dallas, Texas
`May 23-26, 1998
`
`SPONSORED BY
`
`THE ACM SPECIAL INTEREST GROUP FOR
`
`ALGORITHMS AND COMPUTATION THEORY
`
`Hughes, Exh. 1015, p. 2
`
`

`

`Tht Assnciat.ion for CnlllJHiting Machinery
`1515 Broadwa)'
`New York New Yorl< 10036
`
`llJlJX by the Association for Computing Machinery, Inc.(ACM).
`Copyright
`Permission to make digital or hard copies of all or part of this work for
`personal or classroom usc is granted without fee provided that copies
`arc not made or distributed lor profit or coJillnercial advantage and th(lt
`copies bear this notice and the full citation on the first page. To cop~
`othcf\visc. to republish. to post on scrYcrs or to redistribute to lists.
`requires prior specific permission and/or a fcc.
`
`Request permission to republish from: Publications Dept. ACM. Inc. Fa:-; +I (212)
`869-0481 or <pcnnissions(dacm.org>. For other copying of articles that carry a code
`at the bottom or the first or last page. copying is permitted provided that the per-copy
`fee indic(ltcd in the coclc is paid through the Copyright Clearance Center. 222
`Rosewood DriYe. Dall\·crs. MA 01921 .
`
`ACM ISBN: 0-XlJ?lJI-%2-9
`
`Additional copies may be ordered prepaid rrom:
`
`ACM Order Depat·tmcnt
`PO Bo:-; J 1-ll-l
`Church Street Station
`New York. NY I02X(>
`
`Phone : I-800-l -l 2-(JC>2(>
`(US and Canada)
`+ 1-2 12-(>2(>-0.'i()()
`(all other countries)
`fa:-; + 1-212-lJH-1.118
`E-mail: acmpubs(a)acm .org
`
`ACM Order Numher: 50X9XO
`Printed in the USA
`
`Hughes, Exh. 1015, p. 3
`
`

`

`Conference Organization
`
`SIGACT Chair
`
`Jeffrey Vitter
`
`Conference Chairs
`
`Wolf Bein
`
`Steve Tate
`
`Program Chairs
`
`Fan Chung Graham
`
`Treasurer
`
`Lawrence Larmore
`
`Publicity Chair
`
`Ian Parberry
`
`SIGACT Institutional Sponsors
`
`Academic Press, Inc.
`
`A T & T Laboratories
`
`IBM Corporation - T J Watson Research Center
`
`International Thomson Publishing
`
`Lucent Technologiest-Bell Laboratories
`
`Microsoft Research
`
`PWS Publishing Co.
`
`Xerox Corporation- Palo Alto Research Center
`
`iii
`
`Hughes, Exh. 1015, p. 4
`
`

`

`Proceedings of the Thirtieth
`Annual ACM Symposium on Theory of Computing
`May 23- 26, 1998, Dallas, Texas, USA
`
`TABLE OF CONTENTS
`
`Sunday, May 24
`
`Session lA
`On the Limits of Non-Approximability of Lattice Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
`Oded Goldreich and Shaft Goldwasser
`The Shortest Vector Problem in L 2 is NP-Hard for Randomized Reductions .................... 10
`Mikl6s Ajtai
`Quantum Circuits with Mixed States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
`Dorit Aharonov, Alexei Kitaev and Noam Nisan
`
`Session lB
`Exact Sampling and Approximate Counting Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
`Mark L. Huber
`A Polynomial Approximation Algorithm for the Minimum Fill-In Problem .................... 41
`Assaf Natanzon, Ron Shamir and Roded Sharan
`Improved Approximation Algorithms for MULTIWAY CUT ................................. 48
`Gruia Calinescuo, Howard Karloff and Yuval Rabani
`
`Session 2A
`A Framework for Fast Quantum Mechanical Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
`Lov K. Grover
`Quantum vs. Classical Communication and Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
`Harry Buhrman, Richard Cleve and A vi Wigderson
`
`Session 2B
`Finding Maximum Flows in Simple Undirected Graphs is Easier Than Bipartite Matching ....... 69
`David R. Karger and Matthew S. Levine
`Poly-logarithmic Deterministic Fully-dynamic Algorithms for Connectivity, Minimum Spanning tree,
`2-edge and Biconnectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
`Jacob Holm, Kristian de Lichtenberg and Mikkel Thorup
`
`Invited Session I
`Developments in Quantum Computing
`PeterShor
`
`v
`
`Hughes, Exh. 1015, p. 5
`
`

`

`Session 3A
`Approximating the Bandwidth via Volume Respecting Embeddings . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
`Uriel Feige
`Semi-definite Relaxations for Minimum Bandwidth and Other Vertex-ordering Problems
`Avrim Blum, Goran Konjevod, R. Ravi and Santosh Vempala
`Approximation Schemes for the Euclidean k-medians and Related Problem. . . . . . . . . . . . . . . . . . . 106
`Sanjeev Arora, Prabhakar Raghavan and Satish Rao
`Rounding via Tree: Deterministic Approximation Algorithms for Group Steiner Trees and k-median
`...................................................................................... 114
`M. Charikar; C. Chekuri, A. Goel and S. Guha
`
`100
`
`Session 3B
`One Help-bit Doesn't Help .............................................................. 124
`Richard Beigel and Tirza Hirst
`Perfect One-Way Probablilistic Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
`Ran Canetti, Daniele Micciancio and 0. Reingold
`Non-Interactive and Non-Malleable Commitment .......................................... 141
`Giovanni Di Crescenzo, Yuvallshai and Rafail Ostrovsky
`Protecting Data Privacy in Private Information Retrieval Schemes ........................... 151
`Yael Gertner; Yuval /shai, Eyal Kushilevitz and Tal Malkin
`
`Session 4A
`On Approximating Arbitrary Metrics by Tree Metrics
`Yair Barta/
`Trees and Euclidean Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
`Nathan Linial, Avner Magen and Michael Saks
`Random Generation of Embedded Graphs and an Extension to Dobrushin Uniqueness . . . . . . . . . 176
`Marcus Peinado and Thomas Lengauer
`Efficient Algorithms for Constructing Fault Tolerant Geometric Spanners ..................... 186
`Christos Levcopoulos, Giri Narasimhan and Michie/ Smid
`Almost Optimal Dispersers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
`Amnon Ta-Shma
`
`161
`
`Session 4B
`NP Might Not Be As Easy As Detecting Unique Solutions .................................. 203
`Richard Beigel, Harry Buhrman and Lance Fortnow
`The Random Oracle Methodology, Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
`Ran Canetti, Oded Goldreich and Shai Halevi
`Randomized Complexity Lower Bounds .................................................. 219
`D. Grigoriev
`Weak Alternating Automata and Tree Automata Emptiness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
`Oma Kupferman and Moshe Vardi
`Over Words, Two Variables Are as Powerful as One Quantifier Alternation: F02 = E2 n IT2
`
`. • . 234
`
`vi
`
`Hughes, Exh. 1015, p. 6
`
`

`

`Denis Therien and Thomas Wilke
`
`Monday, May 25
`
`Session SA
`Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound . . . . . . . . . . . . . . . . . . . 241
`M. Amin Shokrollahi and Hal Wasserman
`Analysis of Low Density Codes and Improved Designs Using Irregular Graphs . . . . . . . . . . . . . . . 249
`Michael Luby, Michael Mitzenmacher; Amin Shokrollahi and Dan Spielman
`Spot-Checkers ..... . ... . ..... .. ....... . .... . . . . ..... .... .. .... . .. . ... .. .. . . . .. .. .. .... . . 259
`Funda Ergan, Sampath Kannan, S. Ravi Kumar; Ronitt Rubinfeld, and Mahesh Vish(cid:173)
`wanathan
`
`Session SB
`The Power of a Pebble: Exploring and Mapping Directed Graphs , . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
`Michael A. Bender; Antonio Fernandez, Dana Ron, Amit Sahai and Salil Vadhan
`Linear-Time Pointer-Machine Algorithms for LCAs, MST Verification, and Dominators ... .... 279
`Adam L. Buchsbaum, Haim Kaplan, Anne Rogers and Jeffery R. Westbrook
`A Sublinear Bipartitness Tester for Bounded Degree Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
`Oded Goldreich and Dana Ron
`
`Session 6A
`Recycling Queries in PCPs and in Linearity Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
`Luca Trevisan
`The Closure of Monadic NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
`Miklos Ajtai, Ronald Fagin and Larry Stockmeyer
`
`Session 6B
`Information Theoretic Implications for Pairing Heaps . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 319
`Michael L. Fredman
`Min-Wise Independent Permutations . . . . .. .. . . . .. . . . . . . .. . . .. . . . . . . . . . . . .. . . . . . . . . . . .. . . .. 327
`Andrei Broder; Moses Charikar; Alan Frieze and Michael Mitzenmacher
`
`Invited Session II
`The Approximability of NP-hard Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
`Sanjeev Arora
`
`Session 7A
`Algorithms for Capacitated Vehicle Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
`Moses Charikar, Samir Khuller and Balaji Raghavachari
`Adaptive Packet Routing for Bursty Adversarial Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359
`William Aiello, Eyal Kushilevitz, Rafail Ostrovsky and Adi Rosen
`Stability Results for Networks with Input and Output Blocking . .. .. . . .. .. . .... ....... . . . . . .. 369
`
`vi i
`
`Hughes, Exh. 1015, p. 7
`
`

`

`Matthew Andrews and Lisa Zhang
`Randomized Protocols for Low-Congestion Circuit Routing in Multistage Interconnection Networks
`. ...... . .. . .. . ........ .. .. . ... . .. . . .... . . .. . . ..... . . . . . . ... .... .... ... .. .. ...... ..... . 378
`Richard Cole, Bruce M. Maggs, Friedheim Meyer auf der Heide, Michael Mitzen(cid:173)
`macher, Andrea W. Richa, Klaus Schroder, Ramesh K. Sitaraman and Berthold Voeck(cid:173)
`ing
`TCP Dynamic Acknowledgment Delay: Theory and Practice . . ........ .. ....... . ........ .. .. 389
`Daniel R. Dooly, Sally A. Goldman and Stephen D. Scott
`
`Session 7B
`Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge .... . . . 399
`Oded Goldreich, Amit Sahai and Salil Vadhan
`Concurrent Zero Knowledge . . . .... . ............... . .. . ....... ... ....... .. .. . . . ...... . . . . 409
`Cynthia Dwork, Moni Naor and Amit Sahai
`Modular Approach to the Design and Analysis of Key Exchange Protocols . . . . . . . . . . . . . . . . . . . 419
`Mihir Bellare, Ran Canetti and Hugo Krawczyk
`A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs
`.. . .... .. . ....... . .. ...... . .. ........ . ........... .. .... . .... .. . . .. .. ........ ... . .. .... 429
`· Anna Gal
`Checking Polynomial Identities over any Field: Towards a Derandomization? .. ... ............ 438
`Daniel Lewin and Salil Vadhan
`
`RUMP Session
`
`Thesday, May 26
`
`Session SA
`Multicasting in heterogeneous networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
`Amotz Bar-Noy, Sudipto Guha, Joseph (Seffi) Naor and Baruch Schieber
`Minimizing Stall Time in Single and Parallel Disk Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
`Susanne Albers, Naveen Garg and Stefano Leonardi
`On Indexed Data Broadcast .................. . ................................... . . ... ... 463
`Sanjeev Khanna and Shiyu Zhou
`Segmentation Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
`Jon Kleinberg, Christos Papadimitriou and Prabhakar Raghavan
`
`Session SB
`Computing Local Dimension of a Semialgebraic Set ... . ...... .. . . .. .... ...... . ............. 483
`Nicolai Vorobjov
`Asymptotic Acceleration of Solving Multivariate Polynomial System of equations
`B. Mourrain and V. Y. Pan
`A Black Box Approach to the Algebraic Set Decomposition Problem
`Ming-Deh A. Huang and Ashwin J. Rao
`
`488
`
`497
`
`viii
`
`Hughes, Exh. 1015, p. 8
`
`

`

`Are Lower Bounds Easier Over the Reals ? ................................................ 507
`Herve Fournier and Pascal Koiran
`
`Session 9A
`Planar map graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
`Zhi-Zhong Chen, Michelangelo Grigni and Christos Papadimitriou
`Further Algorithmic Aspects of the Local Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524
`Michael Molloy and Bruce Reed
`Decision Algorithms for Unsplittable Flow and the Half-Disjoint Paths Problem .............. 530
`Jon M. Kleinberg
`Improved Approximation Schemes for Traveling Salesman Tours . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
`Satish B. Rao and Warren D. Smith
`
`Session 9B
`Finding Almost-satisfying Assignments ................................................... 551
`Uri Zwick
`On the Complexity of Unsatisfiability Proofs of Random k-CNF Formulas .................... 561
`Paul Beame, Richard Karp, Mike Sales and Toni Pitassi
`k-sat on Groups and Undecidability ....................................................... 572
`Michael H. Freedman
`An Exponential Lower Bound for Depth 3 Arithmetic Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577
`Dima Grigoriev and Marek Karpinski
`
`Session lOA
`A New Composition Theorem for Learning Algorithms .................................... . 583
`Nader H. Bshouty
`Adaptive versus Nonadaptive Attribute-efficient Learning ................................... 590
`Peter Damaschke
`On the Complexity of Protein Folding ..................................... ... ............. 597
`Pierluigi Crescenzi, Deborah Goldman, Christos Papadimitriou, Antonio Piccolboni
`and Mihalis Yannakakis
`
`Session lOB
`Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality . . . . . . . . . . . . 604
`Piotr lndyk and Rajeev Motwani
`Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces .............. 614
`E. Kushilevitz. R. Ostrovsky and Y. Rabani
`Improved Bounds for Acyclic Job Shop Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624
`Uriel Feige and Christian Scheidele
`
`Session llA
`Broadcast Disk Paging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634
`Sanjeev Khanna and Vincenzo Liberatore
`
`ix
`
`Hughes, Exh. 1015, p. 9
`
`

`

`A Deterministic Strongly Polynomial Algorithm for Matrix Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . 644
`Nathan Linial, Alex Samorodnitsky and A vi Wigderson
`
`Session llB
`On Separating the Read-k-Times Branching Program Hierarchy ............................. 653
`Jayram S. Thathachar
`Robust Efficient Distributed RSA-Key Generation ................... . ....... . . . .. ... . .. .... 663
`Yair Frankel, Philip MacKenzie and Moti Yung
`The Cost of the Missing Bit: Communication Complexity with Help ......................... 673
`Laszlo Babai, Thomas Hayes and Peter Kimmel
`Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683
`
`X
`
`Hughes, Exh. 1015, p. 10
`
`

`

`Analysis of Low Density Codes
`and
`Improved Designs Using Irregular Graphs
`
`Michael G. Luby*
`
`Michael Mitzenmachert
`
`M. Amin Shokrollahif
`
`Daniel A. Spielman§
`
`Abstract
`
`In [6], Gallager introduces a family of codes based on sparse
`bipartite graphs, which he calls low-density parity-check codes.
`He suggests a natural decoding algorithm for these codes,
`and proves a good bound on the fraction of errors that can be
`corrected. As the codes that Gallager builds are derived from
`regular graphs, we refer to them as regular codes.
`Following the general approach introduced in [7] for the
`design and analysis of erasure codes, we consider error-correcting
`codes based on random irregular bipartite graphs, which we
`call irregular codes. We introduce tools based on linear pro(cid:173)
`gramming for designing linear time irregular codes with bet-
`ter error-correcting capabilities than possible with regular
`codes. For example, the decoding algorithm for the rate 1/2
`regular codes of Gallager can provably correct up to 5.17%
`errors asymptotically, whereas we have found irregular codes
`for which our decoding algorithm can provably correct up
`to 6.27% errors asymptotically. We include the results of
`simulations demonstrating the effectiveness of our codes on
`systems of reasonable size.
`
`1
`
`Introduction
`
`In [6], Gallager introduces a family of codes based on sparse
`bipartite graphs, which he calls low-density parity-check codes.
`
`• International Computer Science Institute, Berkeley, CA. Parts of this
`research were done while still at the Digital Equipment Corporation Sys(cid:173)
`tems Research Center, Palo Alto, CA. Research partially supported by NSF
`operating grant NCR-9416101. E-mail: luby@ics i . berkeley. edu.
`t Digital Equipment Corporation, Systems Research Center, Palo Alto,
`CA. E-mail: mi chae l m@pa . dec. com.
`*International Computer Science Institute Berkeley, and lnstitut filr In(cid:173)
`formatik der Universitlit Bonn, Germany. Research supported by a Habilita(cid:173)
`tionsstipendium of the Deutsche Forschungsgemeinschaft, Grant Sh 57/1- 1.
`E-mail: amin@icsi . berkeley. edu.
`§Department
`of
`Mathematics,
`E-mail: spielman@math.mit. edu.
`
`M.I.T.
`
`Permission to m;~k,· digit;~ I nr hard c·npic·s nl'all <lr pan nl'this wnrk llw
`p..::rsonal or classroomust· is grankd \\iliH)lll ~ ~~ JlfO\' id~..·d that c~•pi~..·s
`arc nolmadc or dislrihutcd fl1r pmfil or c·nnunc'l'cia l il!h-anl;~ ge and thai
`cnpic~ h~nr thi s noli~~ ;~nd the lilllc,itatinn nnthc lirst page. ·1·., nlp\'
`Olht!r\VISI.!. f() 1\.'pUhJish. (Cl pnst llll SCI'\\.'fS or In 1\.'distrihuh: 1!) Ji st:-:_ .
`n.:quirl.!s prior sp('~o:ilh: p~..·nni ss inn a11d ·'or a I ~·~.·.
`STOC 'JX I );tllas Tl:'\;ts I lSI\
`l'ntl\ ri ght . \('\1 l'i'JX ll·X'J7'J 1-')(.].•J 'J~ ' ... )5.(111
`
`As the codes that Gallager builds are derived from regular
`graphs, we refer to them as regular codes. He suggests a nat(cid:173)
`ural decoding algorithm for these codes, and proves a good
`lower bound on the fraction of errors that can be corrected,
`assuming that there are no short cycles in the underlying
`graph. While much of his work concerns randomly chosen
`graphs, his analysis does not directly apply to such graphs.
`Instead, he constructs explicit graphs of large girth to which
`his analysis does apply.
`The main contribution of this paper is the design and
`analysis of low-density parity-check codes based on irreg(cid:173)
`ular graphs. This work follows the general approach intro(cid:173)
`duced in [7] for the design and analysis of erasure codes.
`There it is shown that using irregular graphs yields codes
`with much better performance than regular graphs. In ac(cid:173)
`cordance with [7], we consider error-correcting codes based
`on random irregular bipartite graphs, which we call irregu(cid:173)
`lar codes. We develop tools based on linear programming
`for designing linear time encodable and decodable irregular
`codes with better error-correcting capabilities than regular
`codes. For example, the rate 1/2 regular codes of Gallager
`can provably correct up to 5.17% errors, whereas we have
`found irregular codes that can provably correct up to 6.27%.
`The only method we currently have for constructing ir(cid:173)
`regular codes is by randomly choosing the irregular graph.
`However, the analysis used by Gallager does not directly ap(cid:173)
`ply to randomly chosen graphs. Thus, to analyze the perfor(cid:173)
`mance of the irregular eodes, we develop an analysis that ap(cid:173)
`plies to randomly chosen graphs. Using techniques from [S]
`for studying random processes, we can calculate for a ran(cid:173)
`dom regular graph the fraction of erroneous bits for which
`Gallager's original algorithm can correct all but an arbitrar(cid:173)
`ily small constant fraction of the errors. Once the number of
`erroneous bits is reduced to this level, we switch from Gal(cid:173)
`lager's algorithm to one used by Spielman and Sipser in [15] ,
`and prove that this new hybrid method successfully finishes
`the decoding with high probability. This analysis easily ex(cid:173)
`tends to the irregular codes that we introduce. Additionally,
`the bound on the probability of error we derive using this
`methodology improves upon the bound derived by Gallager
`for the regular graphs he explicitly constructed.
`
`249
`
`Hughes, Exh. 1015, p. 11
`
`

`

`Gallager's decoding algorithm is a simplification of "be(cid:173)
`lief propagation" [14]. Belief propagation has been exten(cid:173)
`sively tested with Gallager's low-density parity-check codes
`[2, 6, 11, 12, 17] and is strongly related to the highly success(cid:173)
`ful turbo codes [1, 3, 10, 5]. In a separate work, we describe
`empirical tests on irregular codes using a full belief propa(cid:173)
`gation algorithm and demonstrate irregular codes with better
`performance than regular codes [9]. We believe our analy(cid:173)
`sis here provides an important step towards analyzing codes
`based on belief propagation techniques.
`The paper proceeds as follows: in Section 2.1, we present
`a description of regular codes and analyze Gallager's decod(cid:173)
`ing scheme. We show in Section 2.2 how expander-based
`arguments can be used in addition to the previous analysis
`to demonstrate a decoding algorithm that works with high
`probability for regular codes. We introduce irregular codes
`in Section 3, where we demonstrate that our arguments gen(cid:173)
`eralize to irregular codes and describe how to find irregular
`graphs that lead to good codes. In Section 4, we discuss some
`simulation results that show the effectiveness of our analysis
`for designing practical codes. We conclude with a discussion
`of open problems.
`
`2 Regular Codes
`
`2.1 Analyzing Regular Codes
`
`We first review the codes developed by Gallager and his anal(cid:173)
`ysis [6]. Later we explain how his analysis combined with
`the argument from [8] shows that his suggested decoding al(cid:173)
`gorithm corrects all but an arbitrarily small constant fraction
`of the nodes with high probability for random regular codes.
`The decoding algorithm of Gallager's that we analyze is an
`example of hard decision decoding, which signifies that at
`each step the state is derived from local decisions of whether
`each bit is 0 or 1, and this is all the information the state con(cid:173)
`tains (as opposed to more detailed probabilistic information).
`We note that Gallager also proposes a belief propagation type
`decoding algorithm, which uses a more complicated state;
`for more details, see for example [ 4, 9, 11, 17].
`In the following we refer to the nodes on the left and
`right sides of a bipartite graph as its message nodes and check
`nodes respectively. A bipartite graph with n nodes on the left
`and r nodes on the right gives rise to a linear code of dimen(cid:173)
`sion k ~ n -
`r and block length n in the following way:
`the bits of a codeword are indexed by the message nodes. A
`binary vector x = (xi. ... , Xn) is a codeword if and only
`if H x = 0, where H is the r x n incidence matrix of the
`graph whose rows are indexed by the check nodes and whose
`columns are indexed by the message nodes. In other words,
`(xi. ... , Xn) is a codeword if and only if for each check node
`the exclusive-or of its incident message nodes is zero.
`An alternative approach is to allow the nodes on the right
`to represent bits rather than restrictions, and then use a cas(cid:173)
`cading series of bipartite graphs, as described for example
`in [16] or [7]. In this situation, we know inductively the cor-
`
`c<f
`
`check node
`
`messsage node
`
`check nodes
`
`message nodes
`
`Figure 1: Representing the code as a tree.
`
`rect value of the check nodes in each layer when we correct
`the message nodes, and the check nodes are the exclusive-or
`of their incident message nodes.
`
`In the sequel we focus on one bipartite graph only, and
`assume that only the nodes on the left are in error. The anal(cid:173)
`ysis that we provide in this case works for either of the two
`approaches given above, as we may inductively focus on just
`one layer in the context of cascading series of graphs [ 16, 7].
`We call the linear codes that are obtained by either of the
`above constructions regular codes.
`
`Consider a regular random graph with the message nodes
`having degree dt and the check nodes having degree dr.
`With probability p a message node receives the wrong bit.
`The decoding process proceeds in rounds, where in each
`round first the message nodes send each incident check node
`a single bit and then the check nodes send each incident
`message node a single bit. To picture the decoding pro(cid:173)
`cess, consider an individual edge (m, c) between a message
`node m and a check node c, and an associated tree describ(cid:173)
`ing a neighborhood of m. This tree is rooted at m, and the
`tree branches out from the check nodes of m excluding c, as
`shown in Figure 1. For now let us assume that the neighbor(cid:173)
`hood of m is accurately described by a tree for some fixed
`number of rounds.
`
`Each message node m remembers the received bit Tm
`that is purported to be the correct message bit. (Thus, rm is
`not the correct message bit with probability p.) Each edge
`( m, c) remembers a bit 9m,c that is a guess of the correct bit
`of m. This bit is continually updated each round based on all
`information that is passed from c to m. During each round
`a bit is passed in each direction across edge (m, c). Each
`round consists of an execution of the following script:
`
`250
`
`Hughes, Exh. 1015, p. 12
`
`

`

`• For all edges (m, c) do the following in parallel:
`
`- If this is the zeroth round, then set 9m,c to rm.
`- If this is a subsequent round, then 9m,c is
`computed as follows:
`* if all the check nodes of m excluding c
`sent the same value to m in the previous
`round, then set 9m,c to this value,
`* else set 9m,c to rm.
`In either case, m sends 9m,c to c.
`
`-
`
`• For all edges (m, c) do the following in parallel:
`
`-
`
`the check node c sends to m the exclusive-or
`of the values it received in this round
`from its adjacent message nodes excluding m.
`
`Of course the parallel work can easily be simulated se(cid:173)
`quentially. Moreover, the work per round can easily be coded
`so that it is linear in the number of edges.
`Let p1 be the probability that m sends can incorrect value
`9m,c in round i. Initially Po = p. Following the work of
`Gallager, we determine a recursive equation describing the
`evolution of Pi over a constant number of rounds.
`Consider the end of the ith round, and consider a check
`node c' of m other than c. The node d sends m its correct
`value as long as there are an even number (including possibly
`0) message nodes other than m sending c' the wrong bit. As
`each bit was incorrectly sent to c' with probability Pi• it is
`easy to check that the probability that c' receives an even
`number of errors is
`
`(1)
`
`if Pi converges to 0, this does not directly imply that the pro(cid:173)
`cess necessarily corrects all message nodes, even with high
`probability. This is because our assumption that the neigh(cid:173)
`borhood of ( m, c) is accurately represented by a tree for arbi(cid:173)
`trarily many rounds is not true. In fact, even for any constant
`number of rounds it is true only with high probability.
`Gallager proves that, as the block length of the code and
`girth of the graph grow large, this decoding algorithm works
`for all Po < p* . Since random graphs do not have large girth,
`Gallager introduced explicit constructions of regular sparse
`graphs that do have sufficiently large girth for his analysis
`to hold. We will shortly provide an analysis that shows that
`Gallager's decoding algorithm successfully corrects a large
`fraction of errors for a randomly chosen regular graph with
`high probability. Then in Section 2.2 we show how to ensure
`the decoding terminates successfully with high probability
`using a slightly different decoding rule.
`Gallager notes that the decoding rule can be relaxed in
`the following manner: at each round, there is a universal
`threshold value bi (to be determined below) that depends on
`the round number. For each message node m and neighbor(cid:173)
`ing check node c, if at least bi neighbors of m excluding c
`sent the same bit to m in the previous round, then m sends
`this bit to c in this round; otherwise m sends to c its initial bit
`rm. The rest of the decoding algorithm is the same. Using
`the same analysis as for equation (2), we may find a recursive
`description of the Pi· For convenience, we define
`.
`[1+y] t[1 - y]j-1-t
`g(y,t,J) = -2-
`--2-
`
`(3)
`
`Also, for convenience we let Zi = 1 - 2Pi · Then,
`
`Hence, the probability that m was received in error and sent
`correctly in round i + 1 is
`1 + (1- 2pi)dr-l]dt-1
`'
`2
`
`Po
`
`[
`
`(4)
`
`and similarly the probability that m was received correctly
`but sent incorrectly in round i + 1 is given by
`
`(1 - Po)
`
`1 - (1- 2pi)dr-l]dt-1
`2
`
`[
`
`This yields an equation for Pi+ l in terms of Pi:
`
`We choose bi so as to minimize Pi+ 1· To do this we com(cid:173)
`pare the odds of being right initially to the odds of being right
`using the check nodes and the threshold bi. As determined
`by Gallager, the correct choice of bi is the smallest integer
`that satisfies
`
`Pi+l
`
`Gallager's idea is then to find the supremum p* of all
`values of p0 for which the sequence Pi is monotonically de(cid:173)
`creasing and hence converges to 0. Note, however, that even
`
`(2)
`
`Note that bi is an increasing function of Pi ; this is intu(cid:173)
`itive, since as Pi decreases, smaller majorities are needed to
`get an accurate assessment of m's correct value. Also, note
`that while the algorithm functions by passing values along
`the edges, it can also keep a running guess for the value of
`each message node based on the passed values. The algo(cid:173)
`rithm continues until the proposed values for the message
`
`251
`
`Hughes, Exh. 1015, p. 13
`
`

`

`nodes satisfy all the check nodes, at which point the algo(cid:173)
`rithm terminates with the belief that it has successfully de(cid:173)
`coded the message, or it can fail after a preset number of
`rounds.
`It follows simply from a similar argument in [8] that the
`recursive description given by equation (4) is correct with
`high probability over any constant number of rounds.
`Theorem 1 Let i > 0 be an integer constant and let Zi be
`the random variable describing the fraction of edges set to
`pass incorrect messages after i rounds of the above algo(cid:173)
`rithm. Further, let Pi be as given in the recursion (4). Then
`there is a constant c such that for any e > 0 and sufficiently
`large n we have
`Pr(IZi -Pi I > e) < exp( -em).
`
`Proof: We sketch the proof. There are two considerations
`requiring care. First, the neighborhood around a message bit
`m may not take the form of a tree. We show that this does
`not happen too often with an edge exposure martingale ar(cid:173)
`gument. Second, even assuming the number of non-trees is
`small, we still need to prove tight concentration of Pi around
`the expectation given that message bits may be wrong ini(cid:173)
`tially with probability p0 • This follows from a separate mar(cid:173)
`tingale argument, exposing the initial values at each node one
`by one.
`For the first consideration, it is easily seen that there is
`a number "Y depending on i and the maximum degree of
`the graph such that the probability that the neighborhood of
`depth 2i stemming from an edge is not a tree is "Y ln. For
`sufficiently large n the value "Yin is less than el4. Now by
`exposing the edges one by one using an edge exposure mar(cid:173)
`tingale and applying Azuma's inequality [13, Section 4.4] we
`see that the fraction of edges with non-tree neighborhoods is
`greater than el2 with probability at most exp( -em).
`Now let Zi be the expected number of edges set to pass
`incorrect messages afteri rounds. Then IZi- Pi I < el2 with
`high probability by the above. We can show that Zi and Zi
`are close using a martingale argument, exposing the initial
`values at the vertices one by one. Again using Azuma's in(cid:173)
`equality we obtain Pr(IZi - Zil > el2) $ exp( -em) for
`some constant e (depending on