EPFL

Algo+LMA

- Worked on the draft of the journal version of the paper “Analysis of the Second Moment of the LT decoder”.

- Most notable additions to the conference version: detailed introduction; proofs for the derivation of the closed-form expressions for L(x), M(x) and N(x); bounds on the order of the discrepancy terms for C(x), R(x), M(x), L(x) and N(x); bounds on the “dirt” terms in the differential equations.

- Current draft: LT paper.

Starting from a counting argument that shows that there exist double circulant codes that beat the GV bound (not asymptotically), we try to determine the ingredients that made the counting argument work, and improve the bound. We are interested in finding codes 1) with a large automorphism group; 2) where we are viewing the codes as irreducible modules of a group action that has many irreducible modules.

Double circulant codes.

Summary slides.

Can we start with codes with already large automorphism groups to get a better bound? Goppa codes. Bibliography: Thierry Berger, “On the Cyclicity of Goppa Codes, Parity-Check Subcodes of Goppa Codes, and Extended Goppa Codes.”

Graph entropy: defined on graphs with probability distribution on the vertex set. Allows us to use tools such as convex optimization to bound quantities defined on the graph. Can we use graph entropy on the Gilbert graph to improve the GV bound?

Probably not. It looks like getting good bounds using graph entropy would require looking at combinatorial quantities which are difficult to bound, like the chromatic number.

* Some work on randomness in geometric graph setting: starting with random subset, rewriting GV bound in this context, how can we do better.

Generalization of LT codes: instead of each output symbol consisting of one check symbol, we can produce “supersymbols” consisting of a constant number r of checks, produced in an MDS fashion. How does our analysis of ripple and cloud expectation and variance extend to this case?

Generalized LT codes for the case r=2. Expressions for the probability that an element leaves the ripple and the probability that an element leaves the cloud at each decoding step.

unpaid leave.

Studying local testability of affine-invariant codes. Disproved a conjecture that local characterization implies testability by exhibiting a family of affine-invariant codes with a local characterization (hence LDPC) that are not testable with a constant number of queries.

Joint work with Eli Ben-Sasson, Amir Shpilka and Madhu Sudan. Paper: Symmetric LDPC codes are not necessarily locally testable.

Speeding up RS codes in hardware (semester project in ALGO). Previous work by A. Shokrollahi achieves a speedup of RS encoding and some decoding stages, of a factor p when working in a field where there exist p-th roots of unity (at the small additional hardware cost of a DFT unit). We are interested in the case where there exist no roots of unity in the finite field. In this case, we try to build a similar approach by performing computation on additive cosets of a subspace of the field viewed as a vector space (see report filed under January 2011).