EPFL

Algo+LMA

**This is an old revision of the document!**

- Studied the notion of rank-metric codes. In particular, wrote a short proof of optimal rank-distance of Gabidulin codes. Next, understood the use of rank-metric codes for the simultaneous Slepian-Wolf problem.
- While working on the presentation I gave for the start of my work in the ALGO group, proved some lower bounds on the pseudorandomness of small-bias distributions for DNF formulas.

- Helped organize, created the web-page, and attended the workshop “Algebraic Coding Theory”, September 7-9 2011
- Presented in the first session of a reading group consisting of the algo group where we try to understand spatially coupled codes and its possible applications in new communication problems

- Implemented density evolution for spatially-coupled LT codes
- Familiarized myself with techniques of writing more portable codes
- Worked on how to summarize the essential properties of an elastic coding instance, properties that are required for its density evolution analysis
- Wrote code to check whether an instance of elastic coding satisfies the information-theoretic constraints
- Implemented density evolution for elastic spatially coupled codes including a generalization in which each sender can use a spatially coupled LT code with a different parameter

- Considered “expander block codes” which are obtained from a bipartite expander graph. The codeword length is the number of edges in the expander times the block size.
- We considered the case where every vertex (every row or column in the adjacency matrix of the graph) has associated with it an MDS code of a particular length
- Implemented simulator for decoding expander block codes on erasure channels

- Helped my masters semester project student in the various stages of her project, including theoretical understanding of the problem, software settings, simulation approaches
- Worked on understanding the basics of fast matrix multiplication including border rank, asymptotic sum inequality, and that paper (not their later paper) of Coppersmith-Winograd where they get omega < 2.5
- Worked on irregular product codes based on erasure codes, designed a simulator for them, worked on calculating their rate

- Studied the concept of tight-sets and the basics of the Laser method for matrix multiplication
- Worked more on irregular product codes, proved their rate theorem, found their asymptotic analysis, found optimal rate vs. decoding threshold examples in the asymptotic regime, found examples of finite irregular product codes that are better than their regular counterpart
- Worked on three-dimensional irregular product codes

- Worked on the minimum-distance of irregular product codes

- Worked more on irregular product codes with Masoud Alipour, Ghid Maatouk, and Amin Shokrollahi and submitted paper on this work to the ITW conference
- Worked more on generalized LT codes with Ghid Maatouk. Proved that changing Soliton distribution can give capacity-achieving distributions for LT codes where each output packet is obtained from a systematic MDS code of codimension r > 1.

- Prepared a course on Algorithms Design and Analysis
- Wrote a journal-version paper on Goldreich's One-way Function Candidate and Backtracking Algorithms
- Studied and made notes on a combinatorial problem called Langford pairs
- Wrote the draft of a paper on Pseudorandom Generators for Low-Depth Circuits
- Discussed generalized LT codes with Masoud and Ghid
- Study of mathematical basics
- Study of a survey on Pseudorandomness

- Wrote up the proof for generalized ldpc codes that are regular but achieve capacity
- For the above, had to prove a result about the error exponent of the punctured version of a random linear code
- Studied some topology and logic