Lav R. Varshney (IBM T. J. Watson Research Center)
Malleable Coding
Abstract: Reduce, reuse, recycle has become the mantra of the green age and suggests new ways of designing and operating information infrastructures like cloud computing. In this talk, I will present ongoing work on ways of reusing/recycling compressed information that we call malleable coding. A malleable coding scheme considers not only representation length but also ease of representation update, thereby encouraging some form of reuse or recycling to convert an old codeword into a new one. We examine the trade-off between compression efficiency and malleability cost, measured with a string edit distance that introduces a metric topology to the representation domain. We characterize the achievable rates and malleability as the solution of a subgraph isomorphism problem. A distinct formulation of malleable coding where part of an old codeword must be reused in forming the new codeword is also described and a single-letter information-theoretic expression for the achievable rate-malleability region is provided. Connections to the Gacs-Korner common information show that there is a fundamental tension between compression and reuse. Based on joint work with Julius Kusuma (Schlumberger Technology Corporation) and Vivek K Goyal (MIT). |
|
