Secret-sharing over a Network
Arya Mazumdar, University of Minnesota

Sparse Superposition Codes
Florent Krzakala, École Normale Supérieure Paris

Deletion Codes in the High-noise and High-rate Regimes
Carol Wang, Carnegie Mellon University

Non-malleable Codes Against Constant Split-state Tampering
David Zuckerman, University of Texas, Austin

Codes to Mitigate Intercell Interference in Flash Memories
Paul Siegel, UC San Diego

Symmetric Product Codes
Henry Pfister, Duke University

Permutation Codes in the Ulam Metric
Olgica Milenkovic, University of Illinois, Urbana-Champaign

Polar codes provably achieve the symmetric capacity of a memoryless channel while having an explicit construction. The adoption of polar codes however, has been hampered by their mediocre error-correcting performance at short block lengths and the low throughput of their successive-cancellation decoding algorithm. In this talk, we will describe the recent progress along both of these fronts, towards practical polar decoders.

The shared memory emulation problem is a problem studied in distributed computing with applications to distributed storage systems. The multi-version coding problem is a coding theoretic problem that is recently formulated with motivations to shared memory emulation. We will introduce these problems and discuss possible connections in this talk.

Non-volatile memories (NMVs) are becoming increasingly more pervasive, as they are bound to replace hard disk drives in many applications, ranging from consumer electronics to cloud storage. Operational idiosyncrasies of NVMs prevent us from naively using conventional coding schemes. In this talk, we will overview some of recent results on coding-inspired methods for NVMs, including graded bit error correcting codes, WOM codes, constrained rank modulation, dynamic threshold schemes, and optimized graph-based codes. We will also discuss other promising future directions for development of coding (and non-coding)-based methods with applications to NVMs.

Practical storage systems often adopt erasure codes to tolerate device failures and sector failures, both of which are prevalent in the field. However, traditional erasure codes employ device-level redundancy to protect against sector failures, and hence incur significant space overhead. In this talk, I will present a general family of erasure codes called STAIR codes, which efficiently and provably tolerate both device and sector failures without any restriction on the size of a storage array and the numbers of tolerable device failures and sector failures. We propose the upstairs encoding and downstairs encoding methods, which provide complementary performance advantages for different configurations. We conduct extensive experiments to justify the practicality of STAIR codes in terms of space saving, encoding/decoding speed, and update cost.

Recently the notion of locally recoverable code (LRC) was introduced in the field of distributed storage with the goal of combating erasures. Such a code enables a recovery of any symbol of the encoding by accessing a relatively small number of other encoded symbols. In the talk, LRC codes that attain the maximum possible value of the distance for a given locality parameter and code's cardinality will be presented. These codes are based on polynomial evaluations and can be viewed as a natural generalization of Reed-Solomon codes. We will conclude with some extensions of the code construction.

Since the landmark work of Shannon in 1948, error-correcting codes have gained widespread use in communication systems. However, the question of obtaining efficient codes that get arbitrarily close to Shannon capacity with polynomial complexity had remained open for decades. In 2008, Arıkan introduced the technique of channel polarization as a means of constructing explicit capacity-achieving error-correcting codes known as polar codes. A subsequent work of Guruswami and Xia established that for binary-input symmetric memoryless channels, polar codes allow communication rates within epsilon of the Shannon capacity with block length and encoding and decoding complexities all bounded polynomially in 1/epsilon. Polar codes are, therefore, the first explicit construction with such provable guarantees.

However, the question of obtaining similar provable guarantees for q-ary polar codes has remained open. In this work, we resolve this question by extending the result of Guruswami and Xia to q-ary codes. Our high level approach is to do a direct analysis of the convergence rate to capacity by proving an entropic inequality over prime alphabets. Such an inequality was implicit and straightfoward in the q=2 case, as the extremal case of the inequality is known, but for other prime q, the inequality is more subtle due to the lack of a simple characterization of the extremal cases. The polarization result for prime q is then used to obtain the general result for all q by splitting a communication channel into multiple channels over prime alphabets and polarizing each channel separately.

This is joint work with Venkatesan Guruswami.

Reed-Muller codes have recently regained significant attention, from both the computer science and electrical engineering coding communities. As for polar codes, Reed-Muller codes are generated by selecting rows in the tensor product matrix [1,1;0,1]^{\otimes k}, the matrix with Sierpinski triangles on the upper-diagonal. While polar codes are proved to be capacity-achieving, RM codes have long been conjectured to be capacity achieving on symmetric channels, without theoretical validations. We will overview recent results on this conjecture (joint work with A. Shpilka and A. Wigderson), and discuss other code variants (joint work with Y. Wigderson).

Product codes were introduced by Elias in 1954 and generalized by Tanner in 1981. Recently, a number of generalized product codes have been proposed for forward error-correction in high-speed optical communication. In practice, these codes are decoded by iteratively decoding each of the component codes. Symmetric product codes are a subclass of generalized product codes that use symmetry to reduce the block length to roughly half that of a product code with the same component code. When compared to a product code of similar length and rate, this modification can result in improved performance in both the waterfall region and the error floor. A special case of these codes was introduced by Tanner in 1981 and recently called a half-product code by Justesen in 2011. In this talk, we discuss some initial results on symmetric product codes. Our results show that (i) these codes have a larger normalized minimum distance than the product code from which they are derived, (ii) some small constructions achieve the best parameters possible with a linear code, and (iii) extending the construction to tightly-braided block codes achieves similar gains.