Welcome to the Coding Theory Reading Group

Welcome to the Reading Group!

In Spring 2007, we meet weekly on Wednesdays at 5 pm in room 212 Cory.

(Please stay tuned for time/place change.)

Each meeting focuses on a paper (or group of papers) centered around a particular topic. This semester we will start by discussing papers on convex geometry and concentration.
Please see below for the current schedule. 

At the moment, this is an informal reading group, but people involved are expected to read the papers, and take an active role in discussing them.

If you are interested in participating, please email Lara Dolecek at
dolecek@eecs.berkeley.edu

    Date                             Reading Schedule               Presenters
Wed. 2/07
  1. "An Elementary Introduction to Modern Convex Geometry", by K. Ball (pdf),  Lectures 1-2.
               Prasad
Wed. 2/14
  1. "An Elementary Introduction to Modern Convex Geometry", by K. Ball (pdf), Lecture 3.
    2.
              Bobak
Wed. 2/21
    No meeting today.
             
Wed. 2/28
    No meeting today.
             
Wed. 3/07
  1. "An Elementary Introduction to Modern Convex Geometry", by K. Ball (pdf), Lecture 4.
    2.
              Anand
Wed. 3/14
  1. "An Elementary Introduction to Modern Convex Geometry", by K. Ball (pdf), Lecture 5.
    2.
              Galen
Wed. 3/21
  1. "An Elementary Introduction to Modern Convex Geometry", by K. Ball (pdf), Lectures 7 & 8.
    2.
              Charles
Wed. 4/11
  1. "An Elementary Introduction to Modern Convex Geometry", by K. Ball (pdf), Lecture 9.
    2.
              Krish
Wed. 4/18
  1. "A New Look at Independence", by M. Talagrand (pdf), Lecture 9.
    2.
              Prof Wainwright
Wed. 4/25 (at 4 pm !)
  1. "Concentration of Measure Inequalities", by G. Lugosi (pdf), Chapter 4 (also see Chapters 2 and 3 for the background)
    2.
              TBA

    Date                             Reading Schedule               Presenters
9/18
  1. "Network Information Flow", paper by Ahlswede et. al (pdf)
    2.
   Bobak
9/25
  1. "Probabilistic Analysis of LP Decoding" (see broadcast email for paper access)
    2.
   Alex
10/2
  1. [primary] "A Random Linear Network Coding Approach to Multicast" by T. Ho et. al (pdf)
  2. [secondary] "Linear Network Coding " by S. Li, R. Yeung, and N. Cai (pdf)
  3. [secondary] "An Algebraic Approach to Network Coding " by R. Koetter and M. Medard (pdf)
    4.
   Bobak & Alex
10/9
  1. "Randomized Gossip Algorithms", paper by Boyd et al. (pdf)
    2.
   Galen
10/16
  1. "The small world phenomenon: An algorithmic perspective ", paper by J. Kleinberg (pdf)
    2.
   Anand & Alex
10/23
  1. "Computing Separable Functions via Gossip ", paper by D.Mosk-Aoyama and D.Shah (pdf)
    2.
   Prof. Wainwright
10/30
  1. "Database Friendly Random Projections: Johnson-Lindenstrauss With Binary Coins", paper by D.Achlioptas (pdf)
    2.
   Dapo
11/6
  1. [primary] "On Sparse Representation in Pairs of Bases", by A. Feuer and A. Nemirovski (pdf)
  2. [add'l material] " Atomic Decomposition by Basis Pursuit " by S. Chen, D. Donoho and M. Saunders (pdf)
    3.
  3. [add'l material] "A Generalized Uncertainty Principle and Sparse Representation in Pairs of R^N Bases" by M. Elad, A. Feuer and A. Bruckstein (pdf)
    Arash
11/13
    No meeting this week.
  
11/20
  1. "For Most Large Underdetermined Systems of Linear Equations the Minimal L1 Norm Solution is Also the Sparsest Solution" by D. Donoho (pdf)
  2. [supplement] "Notes on Thresholds for Basis Pursuit by M. Wainwright (pdf)
  3. [secondary ref.] "Decoding by Linear Programming" by E. Candes and T. Tao (pdf)
  Prof. Wainwright

    Date                             Reading Schedule               Presenters
2/2 (this meeting is in 258 Cory)
  1. "Asymptotic Enumeration Methods for Analyzing LDPC codes", paper by D. Burshtein and G. Miller (pdf)
  2. "The Average Case Analysis of Algortihms", book by P. Flajolet and R. Sedgewick, Chapters I (pdf) and VI (pdf)
    3.
   Prof. Wainwright & Anand
2/9  
  1. "Asymptotic Enumeration Methods for Analyzing LDPC codes", paper by D. Burshtein and G. Miller (pdf) [Continuation from last time. Focus on material up to Section IVa]
  2. "The Average Case Analysis of Algortihms", book by P. Flajolet and R. Sedgewick, Chapters I (pdf) and VI (pdf) [Continuation from last time. Focus on the first part of Ch1 and Ch6, including Thm. 6.1]
    3.
 Anand & Prof. Wainwright
2/16  
  1. "On the Block Error Probability of LP Decoding of LDPC Codes", paper by R. Koetter and P. O. Vontobel (pdf)
  2. "An Analysis of the Block Error Probability Performance of Iterative Decoding", paper by M. Lentmaier et al. (pdf)
 Alex & Amin
2/23  
    BEARS conference, no meeting this week
 
3/2  
  1. "Analysis of Low Density Parity Check Codes for the Gilbert-Elliott Channel", paper by A. Eckford et al. (pdf)
    2.
 Dan & Lara
3/23  
  1. "Upper Bounds on the Rate of LDPC Codes", paper by D. Burshtein et al. (pdf)
    2.
 Prof. Wainwright
Friday 4/07(please note the meeting is moved to Friday, 4 pm, 531 Cory )  
    Review of Reed-Solomon Codes. References:
  1. See standard books like Lin & Costello and Wicker and
  2. M. Sudan's class notes (here) [specifically, lectures 4, 10, 11 and 13]
 Lara
Monday. 4/17(please note the meeting is moved to Mon. 5 pm in 476 Cory)  
  1. "Decoding of Reed-Solomon Codes Beyond the Error Correction Bound" paper by M. Sudan (pdf)
    2.
 Anand
4/20(the usual time and place: Thursday 5 pm, 531 Cory)  
  1. "Improved Decoding of Reed-Solomon and Algebraic Geometry Codes" paper by V. Guruswami and M. Sudan (pdf)
  2. "Algebraic Soft Decision Decoding of Reed-Solomon Codes" paper by R. Koetter and A. Vardy (pdf)
    3.
 Vinod
4/27  
    2. Upper Bound on Rate for Low Density Codes. See pp.37-38 in R. Gallager's thesis (link here)
  2. "On the Complexity of Reliable Communication on the Erasure Channel" paper by A. Khandekar and R. McEliece (pdf)
  3. Complexity Analysis. See Section 3.6, pp.67-72 in A. Khandekar's thesis (link here)
    4.
  4. " Parity check density versus performance of binary linear block codes over memoryless symmetric channels" paper by I. Sason and R. Urbanke (pdf)
 Pulkit

For the list of topics/papers discussed in Fall 2005, please see below.

Date Reading Schedule  Presenter(s)
9/20, Tues.
  1. "The Generalized Distributive Law" by S.M. Aji and R.J. McEliece (pdf)
  2. "Factor Graphs and the Sum-Product Algorithm" by F.R. Kschischang, B.J. Frey, and H.A. Loeliger (pdf)
  Prof. Wainwright
10/5,
Wed.
  1. "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms" by J. Yedidia, W. Freeman, and Y. Weiss (pdf)
 Lara
10/12, Wed.
  1. "Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms" by J. Yedidia, W. Freeman, and Y. Weiss (continuation from last time) (pdf)
  2. "Belief Propagation on Partially Ordered Sets" by R. J. McEliece and M. Yildrim (pdf)
 Lara
10/19, Wed.
  1. "Nested Linear/Lattice Codes for Structured Multiterminal Binning "by Zamir et al. (pdf)
 Prof. Wainwright
10/26, Wed.
  1. "Nested Linear/Lattice Codes for Structured Multiterminal Binning "by Zamir et al. (continuation) (pdf)
 Anand & Bobak
11/2, Wed.
  1. "Nested Linear/Lattice Codes for Structured Multiterminal Binning "by Zamir et al. (continuation) (pdf)
  2. For more on dirty paper problem see pp. 454-464, Ch. 10 in "Fundamentals of Wireless Communication", by D. Tse and P. Viswanath (supplement material) (link to online pdf)
 Bobak & Vinod
11/16, Wed.
  1. EXIT charts for the binary erasure channel, see Ch. 2 in the " Modern Coding Theory " book by T. Richardson and R. Urbanke (link to book's website)
 Alex
11/23, Wed.
    Thanksgiving break, no meeting
 
11/30, Wed.
  1. EXIT charts for the binary erasure channel, see Ch. 2 in the " Modern Coding Theory " book by T. Richardson and R. Urbanke (continuation) (link to book's website)
  2. "Extrinsic Information Transfer Function: Model and Erasure Channel Properties" by A. Ashikhmin, G. Kramer and S. ten Brink (pdf)
 Alex & Dan

For the list of topics/papers discussed in Spring 2005, please see below.

Date Reading Schedule  Presenter(s)
3/8
  1. "The Generalized Distributive Law" by S.M. Aji and R.J. McEliece (pdf)
  2. "Factor Graphs and the Sum-Product Algorithm" by F.R. Kschischang, B.J. Frey, and H.A. Loeliger (pdf)
  Dan & Assane
3/24, Thur.

at 3 pm
  1.  "The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding"   by T. J. Richardson  and R. L.   Urbanke (pdf)
  Alex & Lara
4/5
  1. "The Capacity of Low-Density Parity-Check Codes Under Message-Passing Decoding"   by T. J. Richardson  and R. L.   Urbanke (pdf)   (the remainder)
  2. "Design of Capacity-Approaching Irregular Low-Density Parity- Check Codes" by T.J. Richardson, M.A. Shokrollahi, and R.L. Urbanke (pdf)
  Alex & Lara

 Pierre
4/19
  1. "Design of Capacity-Approaching Irregular Low-Density Parity Check Codes "   by T. J. Richardson, M.A. Shokrollahi, and R. L.   Urbanke (pdf)  
  2. "Expander Codes" by M. Sipser and D. Spielman (pdf) [Background reference is "Modern Coding Theory", Ch.9 by R&U (ps) ]
  Pierre

 TBA
5/10
  1. "Expander Codes" by M. Sipser and D. Spielman (pdf) [Background reference is "Modern Coding Theory", Ch.9 by R&U (ps) ]
  Salman