Technical Program

Paper Detail

Paper IDO.1.5
Paper Title $O(\log \log n)$ Worst-Case Local Decoding and Update Efficiency for Data Compression
Authors Shashank Vatedka, Indian Institute of Technology Hyderabad, India; Venkat Chandar, DE Shaw, United States; Aslan Tchamkerten, Telecom Paris, France
Session O.1: Data Compression
Presentation Lecture
Track Source Coding
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract This paper addresses the problem of data compression with local decoding and local update. A compression scheme has worst-case local decoding $ d_{wc} $ if we can recover any bit of the raw file by probing at most $ d_{wc} $ bits of the compressed sequence, and has update efficiency of $u_{wc} $ if a single bit of the raw file can be updated by modifying at most $ u_{wc} $ bits of the compressed sequence. This article provides an entropy-achieving compression scheme for memoryless sources that simultaneously achieves $ O(\log\log n) $ local decoding and update efficiency. Key to this achievability result is a novel succinct data structure for sparse sequences which allows efficient local decoding and local update. Under general assumptions on the local decode and update algorithms, a converse result shows that the maximum of $ d_{wc} $ and $ u_{wc} $ must grow as $ \Omega(\log\log n) $.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!