Coding: From Practice to Theory
2015-02-19..2015-02-24
Berkeley, United States
who it's for
storage engineers, distributed systems engineers, coding theory researchers, reliability engineers, hardware designers, data center architects
topics
polar codes finite-length performance; spatially coupled LDPC codes; locally recoverable codes constructions; erasure codes for streaming communication; codes for DNA-based storage; multi-version coding for storage systems; STAIR sector-and-device codes; deletion codes in high-noise regimes; sparse superposition codes for AWGN; approximate message passing for compressed sensing; CRC-aided list decoding implementations; deterministic rateless codes for BSC
| title | author | length |
|---|---|---|
| Statistical Estimation on Graphs | Andrea Montanari | 31m |
Random LDPC code (rate 1/2, degree 3/6) shows a sharp gap between the local decoder threshold (belief propagation) and the information-theoretic threshold… | ||
| Are Polar Codes Practical? | Warren Gross | 30m |
Successive cancellation decoding is serial and looks like N log N work but schedules down to about N and then to a small constant number of PEs, so hardware is… | ||
| The Edge Removal Problem | Mike Langberg | 30m |
Asks whether removing a directed edge of capacity δ always reduces every achievable rate by at most δ and frames an edge removal conjecture that is open… | ||
| Multi-version Coding and Shared Memory Emulation | Viveck Cadambe | 31m |
Compares ABD replication to a formal multiversion coding model with n servers, V versions, C connectivity and shows coding must store multiple versioned… | ||
| Structural Properties of Erasure Codes for Streaming Communication | Ashish Khisti | 31m |
Defines a sliding-window channel model that allows either a burst of length B or up to N isolated erasures in any window W and proves an upper bound… | ||
| New Problems in Coding Theory with Applications to Modern Data Storage and Memories | Lara Dolecek | 34m |
Measurements on a TLC device (TLC (3 bits/cell)) show raw wear-out can kill lifetime in months and errors concentrate as one bit per symbol. A construction… | ||
| A Theory of Polarization | Emre Telatar | 31m |
Constructive proof that repeated two-channel transform produces synthetic channels whose capacities polarize to near 0 or 1 and whose fraction of near-1… | ||
| Codes for Distributed Storage: Recent Results | P Vijay Kumar | 27m |
Two concrete results: a high‑rate MSR construction that achieves rate = (T-1)/T with n = T·Q, k = (T-1)Q, d = n−1 and sub‑packetization alpha = Q^T, beta =… | ||
| Storage Codes and Data Retrieval | Emina Soljanin | 29m |
Compares queuing models for coded storage and measures download latency using simulations and analysis: a 10K fork-join simulation with K=1,5,10 shows… | ||
| STAIR Codes: A General Family of Erasure Codes for Tolerating Device and Sector Failures in ... | Patrick Pat-Ching Lee | 30m |
Proposes Stair codes: a family that combines two MDS codes (row and column) to tolerate m full-disk failures plus a bounded pattern of s sector failures… | ||
| Spatial Coupling vs. Block Coding: A Comparison | Daniel Costello | 31m |
Describes spatially coupled LDPC constructed from protographs by edge spreading (example m=2) and lifted with permutation matrices, showing threshold… | ||
| Coding for DNA-based Storage Systems | Olgica Milenkovic | 36m |
Built a working rewritable and random-access DNA storage prototype that stores UIUC/Wikipedia fragments, uses G‑block assembly, overextension PCR for editing… | ||
| Coding Theory for Scalable Media Delivery | Michael Luby | 33m |
Claims useable fountain coding: a RaptorQ systematic fountain code is broadcast as repair symbols only while devices fetch small HTTP prefixes to complete… | ||
| Deletion Codes in the High-noise and High-rate Regimes | Carol Wang | 33m |
Constructs explicit deletion codes using explicit concatenated construction that pairs a Reed-Solomon outer + dense inner code with small constant headers or… | ||
| Locally Recoverable Code Constructions and Some Extensions | Itzhak Tamo | 34m |
Constructs LRCs that meet the distance bound with equality while keeping field size ~ n, using a Reed‑Solomon style encoding where a degree‑(r+1) polynomial G… | ||
| List Recovery and Local Decoding of Expander Codes | Mary Wootters | 27m |
Shows that taking a D‑regular Ramanujan expander and an inner code with modest local structure yields an outer Tanner/expander code with concrete guarantees… | ||
| Polar Codes over q-ary Alphabets and Polynomially Fast Convergence to Shannon Capacity | Ameya Velingker | 34m |
Shows that q-ary polar codes over prime-size alphabets achieve capacity with block length polynomial in 1/epsilon and encoding/decoding time N log N, but the… | ||
| A Student's View of Locally Repairable Codes | Arya Mazumdar | 27m |
Student-oriented survey argues that locality forces the same gap to erasure‑channel capacity as LDPC codes, proving locality must grow like log(1/ε) when rate… | ||
| Reed-Muller and Other Subcodes of the Sierpinski Matrix | Emmanuel Abbe | 32m |
Reed–Muller rows are reinterpreted via the Sierpinski tensor and a polarization of conditional ranks to build explicit parity matrices that meet a… | ||
| Non-malleable Codes Against Constant Split-state Tampering | David Zuckerman | 30m |
Constructs the first explicit constant-rate for c=10 non-malleable code in the c split-state model, with exponentially small error and an efficient encoder… | ||
| Deterministic Rateless Codes for BSC | Guy Even | 32m |
Explicit rateless construction for the binary symmetric channel that outputs a systematic infinite generator matrix whose next row is computed… | ||
| Sparse Superposition Codes for the AWGN Channel, Message Passing, Replica and Spatial Coupling | Florent Krzakala | 37m |
Sparse superposition codes encode messages as L sections of size B with one nonzero entry, then multiply by a random or Hadamard matrix and send over AWGN… | ||
| Symmetric Product Codes | Henry Pfister | 33m |
Defines a half product code as the antisymmetric subcode of a square product code: entries on the diagonal are forced to zero so length and dimension drop… | ||
| Gap to Capacity of Finite Length Polar Codes | David Burshtein | 33m |
Extends finite-length polar scaling from binary to q-ary channels and gives a concrete numerical method: compute a concave upper bound on the… | ||
| nothing matches | ||