Still on RS speedup project. Trying another approach based on the existence of a “good” primitive element.



  • Working on new version of LT paper for IEEE Transactions.
  • Working on joint publication with Eli Ben-Sasson, Elena Grigorescu, Amir Shpilka, and Madhu Sudan. We study properties of affine-invariant families and prove that 1) sums of single-orbit characterized properties is also single-orbit characterized, and 2) the property or n-variate low-degree polynomials is single-orbit characterized.

March, April

  • Still working on affine-invariant families with Ben-Sasson, Grigorescu, Shpilka and Sudan. The final paper On sums of locally testable affine-invariant properties was accepted for publication in the conference Approx/Random 2011.
  • The bigger and much more difficut question remains: can we fully characterize families locally testable affine-invariant properties? We conjecture that all locally testable affine-invariant properties are of the form single-orbit property + sparse polynomial.

April, May

  • New line of work related to the RS speedup problem: instead of generalizing the method of Shokrollahi to fields where there are no roots of unity, we go back to fields with roots of unity and try to parallelize the syndrome computations. The goal is to find an appropriate transformation of the syndrome matrix so that we end up with a block-diagonal matrix where we can apply the same (or very similar circuitry) for each block.
  • One possible approach: the syndrom matrix, up to permutation, is a block-circulant matrix where each block is again a circulant matrix. Is there a way to relate the displacement rank of the syndrome matrix to those of the smaller matrices? Studying displacement rank and finding kernel elements of matrices with the displacement method.


  • Attended the Conference on Computational Complexity (CCC), San Jose, USA. Presented joint publication with Ben-Sasson, Shpilka and Sudan. Slides.
  • Still working on parallelizing syndrome computations for the RS speedup.
  • Working with Christina Fragouli, Vinod Prabhakaran and Yasin Büyükalp (a student we're supervising) on a project that extends some work I did under supervision of Christina and Vinod in the Network Coding class I took last Fall. We define a new security criterion for network coding, namely, intermediate nodes not learning “more than they should”, and use one-time pads to ensure security. Previously I gave an algorithm that ensures security over a special kind of combination network and we think it is optimal. We study lower bounds on the minimum info that must be transmitted among sources to ensure security, and try to formulate some algorithms.


  • Participated in the workshop “Aspects of Coding Theory”, EPFL.
  • Working on parallelizing syndrome computations, but it looks like this is going nowhere.
  • Still working on the network coding project with Christina, Vinod and Yasin.
  • Starting to look at spatially-coupled codes.


  • Attended APPROX/RANDOM 2011 (Princeton University).
  • Visited Madhu Sudan at Microsoft Research.
  • Working with Sudan on Conjecture 5.9 in our paper [BGMSS] (see March above). It turns out the sets of degrees indexing the rows in our case relate to so-called “interpolating exponent sets” studied by Shokrollahi. Trying to see if we can find tools in this direction to prove our conjecture, which in turn would basically imply that locally testable families that are not low-degree polynomials must be sparse.
  • Still working on the secure network coding project.


  • Participated in the workshop “Algebraic Coding Theory”, September 7-9, EPFL. Gave a talk about our results in [BMSS] publication.
  • Reading up on spatially coupled codes; organizing an informal internal seminar to discuss them. One question is finding a simple explanation to why they perform so well and thinking of the finite length case.
  • Still working on the secure network coding project.


  • Final version of the LT paper. Took a lot of restructuring. We now have a main lemma that we apply for the derivation of the closed-form formula for all the quantities of interest. The paper was accepted for publication in the IEEE Transactions on Information Theory.
  • One main reason for looking at spatially coupled codes is that they might be useful to solve the following Slepian-Wolf-like problem: two senders with correlated files, receiver wants to reconstitute both files with side information. Devise a coding method with minimal overhead that allows the receiver to reconstitute both files no matter where the correlated indices and the side info indices are. This problem can be generalized to that of “elastic codes”, defined by Luby and Shokrollahi. They give a tight algebraic solution to the SW problem, but at the cost of a huge field size. We are trying (with Omid) to look at a possible application of spatially coupled codes to solve this problem.


  • Participated in the Dagstuhl seminar “Coding Theory” (November 14-18).
  • Still looking at elastic codes and applicability of spatially coupled codes. Another approach we're looking at is using rateless codes (eg, Raptor codes) to solve the Slepian Wolf problem.


  • Working with Omid and Masoud on a generalization of product codes. The starting point was work on staircase codes by Kschischang et al and Amin's idea that allowing for irregularity in these or similar constructions might lead to better performance. In the case of product codes, allowing row and column codes of different and carefully designed rates might lead to better error correction without sacrificing in the overall rate of the code. The properties (rate, threshold) of these codes are not trivial to deduce. So far we have an intuitive encoding algorithm for a systematic version of irregular product codes and we are trying to derive the tightest bounds on the rate of the code. We are also running simulations for very small codes to find the best rate distributions for these codes.