Internet of Things devices have become highly popular thanks to the services they offer. However, they also raise privacy concerns since they share fine-grained time-series user data with untrusted third parties. We model the user鈥檚 personal information as the secret variable, to be kept private from an honest-but-curious service provider, and the useful variable, to be disclosed for utility.
Motivated by DNA-based applications, we generalize the bee identification problem proposed by Tandon et al. (2019). In this setup, we transmit all $M$ codewords from a codebook over some channel and each codeword results in $N$ noisy outputs. Then our task is to identify each codeword from this unordered set of $MN$ noisy outputs. First, via a reduction to a minimum-cost flow problem on a related bipartite flow network called the input-output flow network, we show that the problem can be solved in $O(M^{3})$ time in the worst case.
Private information retrieval (PIR) protocols allow a user to retrieve a data item from a database without revealing any information about the identity of the item being retrieved. Specifically, in information-theoretic $k$ -server PIR, the database is replicated among $k$ non-communicating servers, and each server learns nothing about the item retrieved by the user. The effectiveness of PIR protocols is usually measured in terms of their communication complexity, which is the total number of bits exchanged between the user and the servers.
Let $A(n, d)$ denote the maximum size of a binary code of length $n$ and minimum Hamming distance $d$ . Studying $A(n, d)$ , including efforts to determine it as well to derive bounds on $A(n, d)$ for large $n$ 鈥檚, is one of the most fundamental subjects in coding theory. In this paper, we explore new lower and upper bounds on $A(n, d)$ in the large-minimum distance regime, in particular, when $d = n/2 - \Omega (\sqrt {n})$ .
Generalized integrated interleaved (GII) codes are essential to next-generation digital communication and storage systems since they can achieve very high decoding throughput with low complexity. Only hard-decision GII decoding has been considered in previous work. To further improve the error-correcting capability, soft-decision decoding algorithms utilizing the channel probability information need to be developed. The decoding of GII codes constructed based on BCH codes consists of multiple rounds of BCH decoding.
The bee-identification problem, formally defined by Tandon, Tan, and Varshney (2019), requires the receiver to identify 鈥渂ees鈥 using a set of unordered noisy measurements. In this previous work, Tandon, Tan, and Varshney studied error exponents and showed that decoding the measurements jointly results in a significantly larger error exponent. In this work, we study algorithms related to this joint decoder. First, we demonstrate how to perform joint decoding efficiently.
Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels and are conjectured to have a comparable performance to that of random codes in terms of scaling laws. However, such results are established assuming maximum-likelihood decoders for general code parameters. Also, RM codes only admit limited sets of rates. Efficient decoders such as successive cancellation list (SCL) decoder and recently-introduced recursive projection-aggregation (RPA) decoders are available for RM codes at finite lengths.
In this paper, we first formulate a novel Chase Guruswami-Sudan algorithm which list corrects not only all errors among the Chase flipping symbols but also the number of errors up to the enhanced Johnson bound among remaining positions, for Reed-Solomon and $q$ -ary BCH codes. The enhanced Johnson bound is induced by shortening the code without those Chase flipping symbols. We next devise a novel Chase K枚tter-Vardy algorithm for soft decision decoding of Reed-Solomon codes.
Motivated by applications in distributed storage, the notion of a locally recoverable code (LRC) was introduced a few years back. In an LRC, any coordinate of a codeword is recoverable by accessing only a small number of other coordinates. While different properties of LRCs have been well-studied, their performance on channels with random erasures or errors has been mostly unexplored. In this paper, we analyze the performance of LRCs over such stochastic channels.
We propose a new compression scheme for genomic data given as sequence fragments called reads. The scheme uses a reference genome at the decoder side only, freeing the encoder from the burdens of storing references and performing computationally costly alignment operations. The main ingredient of the scheme is a multi-layer code construction, delivering to the decoder sufficient information to align the reads, correct their differences from the reference, validate their reconstruction, and correct reconstruction errors.