Data Compression with Private Local Decodability

Classical compression schemes suggest that message symbols cannot be privately decoded; if a string X n is encoded into a codeword C nR at a non-trivial rate R, then the decoding of an individual symbol X i reveals information about the rest of the symbols X n \X i .While this holds for virtually al...

Full description

Saved in:
Bibliographic Details
Main Authors: Chandar, Venkat, Tchamkerten, Aslan, Vatedka, Shashank
Format: Conference Proceeding
Language:English
Subjects:
Data compression
Decoding
Hamming weight
Symbols
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Classical compression schemes suggest that message symbols cannot be privately decoded; if a string X n is encoded into a codeword C nR at a non-trivial rate R, then the decoding of an individual symbol X i reveals information about the rest of the symbols X n \X i .While this holds for virtually all lossless compression schemes, it is shown that this need not be the case. This paper proposes a lossless compression scheme for bit strings with the following properties. For any sufficiently small p > 0, it encodes each length-n bit string of Hamming weight at most np into a binary codeword of length O\left( {np{{\log }^2}\frac{1}{p}} \right) such that the subset of compressed bits that need to be probed in order to decode a particular message bit reveals no additional information about the other message bits.
ISSN:2157-8117
DOI:10.1109/ISIT54713.2023.10206999