Abstract

A private information retrieval protocol (PIR) scheme under an arbitrary collusion pattern (mc{P}) enables a client to retrieve one message from a library of (K) equal-sized messages duplicated in (N) servers, while keeping the index of the desired message private from any colluding set in (mc{P}). The efficiency of a PIR protocol is measured by its rate, defined as the ratio of the message size to the total download cost, and the supremum of all the achievable rates is the capacity of PIR. Although achieving high rates typically requires sufficiently large message sizes, smaller message sizes also desirable due to reduced implementation complexity and fewer constraints. By characterizing the capacity-achieving schemes, Tian, Sun, and Chen (2019) showed that the optimal message size for uniformly decomposable PIR schemes under no-collusion setting is (N-1). However, comparable results are not yet available for more general collusion settings.

In this work, we present a complete characterization of the properties of capacity-achieving decomposable PIR schemes under arbitrary collusion patterns. Building on this characterization, We derive a general lower bound on the optimal message size for capacity-achieving uniformly decomposable PIR schemes under an arbitrary collusion pattern (mc{P}), expressed in terms of the hitting number of a newly defined family of subsets of servers determined by the collusion pattern (mc{P}). Finally, we specialize the lower bound to several important classes of collusion patterns, including (T)-collusion, disjoint collections of colluding sets, cyclically (T)-contiguous collusion, and disjoint collections of cyclically contiguous colluding sets. For the last two collusion patterns, we present matching achievable schemes that attain the corresponding bounds, thereby providing a complete characterization of the optimal message size under these collusion patterns.

Abstract

We design new minimal-subpacketization schemes for
information-theoretic Private Information Retrieval on graph-
based replicated databases. In graph-based replication, the
system consists of K files replicated across N servers according
to a graph with N vertices and K edges. The client wants to
retrieve one desired file, while keeping the index of the desired
file private from each server via a query-response protocol.
We seek PIR protocols that have (a) high rate, which is the
ratio of the file-size to the total download cost, and (b) low
subpacketization, which acts as a constraint on the size of the
files for executing the protocol. We report two new schemes
which have unit-subpacketization (which is minimal): (i) for a
special class of graphs known as star graphs, and (ii) for general
graphs. Our star-graph scheme has a better rate than previously
known schemes with low subpacketization for general star
graphs. Our scheme for general graphs uses a decomposition
of the graph via independent sets. This scheme achieves a rate
lower than prior schemes for the complete graph, however it
can achieve higher rates than known for some specific graph
classes.

Abstract

The problem of blind identification of channel codes
at a receiver involves identifying a code chosen by a transmitter from a known code-family, by observing the transmitted codewords through the channel. Most existing approaches for code-identification are contingent upon the codes in the family having some special structure, and are often computationally
expensive otherwise. Further, rigorous analytical guarantees on the performance of these existing techniques are largely absent. This work presents a new method for code-identification on the
binary symmetric channel (BSC), inspired by the framework of subspace codes for operator channels, carefully combining principles of hamming-metric and subspace-metric decoding. We refer to this method as the minimum denoised subspace discrepancy decoder. We present theoretical guarantees for code-identification using this decoder, for bounded-weight errors, and also present a bound on the probability of error when used on the BSC. Simulations demonstrate the improved performance of our decoder for random linear codes beyond existing general-purpose techniques, across most channel conditions and even
with a limited number of received vectors.

Abstract

Building on the well-established capacity-achieving schemes of Sun-Jafar (for replicated storage) and the closely related scheme of Banawan-Ulukus (for MDS-coded setting), a recent work by Anand et al. proposed new classes of weak private information retrieval (WPIR) schemes for the collusion-free (replication and MDS-coded) setting, as well as for the $T$-colluding scenario. In their work, Anand et al. characterized the expressions for the rate-privacy trade-offs for these classes of WPIR schemes, under the mutual information leakage and maximal leakage metrics. Explicit achievable trade-offs for the same were also presented, which were shown to be competitive or better than prior WPIR schemes. However, the class-wise optimality of the reported trade-offs were unknown. In this work, we show that the explicit rate-privacy trade-off under the mutual information leakage metric, reported for the Sun-Jafar-type scheme by Anand et al. are class-wise optimal for the non-colluding and replicated setting. Furthermore, we prove the class-wise optimality for Banawan-Ulukus-type MDS-WPIR and Sun-Jafar-type $T$-colluding WPIR schemes, under threshold-constraints on the system parameters. When these threshold-constraints do not hold, we present counter-examples which show that even higher rates than those reported before can be achieved.

Abstract

In pliable index coding (PICOD), a number of clients are connected via a noise-free broadcast channel to a server which has a list of messages. Each client has a unique subset of messages at the server as side-information, and requests for any one message not in the side-information. A PICOD scheme of length ℓ is a set of ℓ encoded transmissions broadcast from the server such that all clients are satisfied. Finding the optimal (minimum) length of PICOD and designing PICOD schemes that have small length are the fundamental questions in PICOD. In this paper, we present a new lower bound for the optimal PICOD length using a new structural parameter called the nesting number, denoted by η(H) associated with the hypergraph H that represents the PICOD problem. While the nesting number bound is not stronger than previously known bounds, it can provide some computational advantages over them. Also, using the nesting number bound, we obtain novel lower bounds for some PICOD problems with special structures, which are tight in some cases. A complete version with all proofs is available online [1].

Abstract

In pliable index coding (PICOD), a number of clients are connected via a noise-free broadcast channel to a server which has a list of messages. Each client has a unique subset of messages at the server as side-information, and requests for any one message not in the side-information. A PICOD scheme of length ℓ is a set of ℓ encoded transmissions broadcast from the server such that all clients are satisfied. Finding the optimal (minimum) length of PICOD and designing PICOD schemes that have small length are the fundamental questions in PICOD. In this paper, we use a hypergraph-based approach to derive new achievability and converse results for PICOD(t), where clients request t new messages (for some t ≥ 1). We present a simple greedy algorithm for PICOD(1), termed DelGreedy, which gives an achievable linear scheme with length at most Δ(H), where Δ(H) is the maximum degree of any vertex in the hypergraph H that represents the PICOD problem. We then extend this idea to obtain an achievable scheme for PICOD(t). We also give a lower bound for the optimal PICOD length using a new structural parameter associated with the PICOD hypergraph called the nesting number, denoted by η(H). While the nesting number bound is not stronger than previously known bounds, it can provide some computational advantages over them. Also, using the nesting number bound, we also obtain novel lower bounds for some PICOD problems with special structures, which are tight in some cases. We also characterize the optimal PICOD lengths for problems with Δ(H) ∈ {1, 2, 3}, and for problems with upto three clients. Further, we present a class of PICOD problems to show that the gap between the lower bound η(H) and the achievable PICOD length from DelGreedy algorithm can be arbitrarily large. Finally, we demonstrate the achievable PICOD lengths from our algorithms via simulations on randomly generated PICOD problems, and compare it with existing algorithms. We observe that DelGreedy performs better than some existing algorithms, while being worse than others, in terms of the code length achieved. Specifically, the greedy-cover based algorithm from a prior work of Brahma and Fragouli performs better, achieving lengths 1.5x-2x smaller than DelGreedy. However, the DelGreedy algorithm demonstrates 1.5x-3x faster running times than GRCOV, providing an alternative point in the rate-computation tradeoff of PICOD code design. These results extend to the PICOD(t) scenario also, with the improvements in computation-time over pre-existing algorithms being more dramatic in some cases.

Abstract

We introduce Berman-intersection-dual Berman (BiD) codes. These are abelian codes of length $3^m$ that can be constructed using Kronecker products of a $3 times 3$ kernel matrix. BiD codes offer minimum distance close to that of Reed-Muller (RM) codes at practical blocklengths, and larger distance than RM codes asymptotically in the blocklength. Simulations of BiD codes of length $3^5=243$ in the erasure and Gaussian channels show that their block error rates under maximum-likelihood decoding are similar to, and sometimes better, than RM, RM-Polar, and CRC-aided Polar codes.

Abstract

The shotgun sequencing process involves fragmenting a long DNA sequence (input string) into numerous shorter, unordered, and overlapping segments (referred to as reads). The reads are sequenced and later aligned to reconstruct the original string. Viewing the sequencing process as the read-phase of a DNA storage system, the information-theoretic capacity of noise-free shotgun sequencing has been characterized in literature. Motivated by the base-wise quality scores available in practical sequencers, a recent work considered the shotgun sequencing channel with erasures, in which the symbols in the reads are assumed to contain random erasures. Achievable rates for this channel were identified. In the present work, we obtain a converse for this channel. The arguments for the proof involve a careful analysis of a genie-aided decoder, which knows the correct ordering of the reads. The converse is not tight in general; however, it meets the achievability result asymptotically in some channel parameters.

Abstract

In information-theoretic private information retrieval (PIR), a client wants to retrieve one desired file out of $M$ files, stored across $N$ servers, while keeping the index of the desired file private from each $T$-sized subset of servers. A PIR protocol must ideally maximize the rate, which is the ratio of the file size to the total quantum of the download from the servers, while ensuring such privacy. In Weak-PIR (WPIR), the criterion of perfect information-theoretic privacy is relaxed. This enables higher rates to be achieved, while some information about the desired file index leaks to the servers. This leakage is captured by various known privacy metrics. By leveraging the well-established capacity-achieving schemes of Sun and Jafar under non-colluding ($T=1$) and colluding ($1<Tleq N$) scenarios, we present WPIR protocols for these scenarios. We also present a new WPIR scheme for the MDS scenario, by building upon the scheme by Banawan and Ulukus for this scenario. We present corresponding explicit rate-privacy trade-offs for these setups, under the mutual-information and the maximal leakage privacy metrics. In the collusion-free setup, our presented rate-privacy trade-off under maximal leakage matches that of the previous state of the art. With respect to the MDS scenario under the maximal leakage metric, we compare with the non-explicit trade-off in the literature, and show that our scheme performs better for some numerical examples. For the $T$-collusion setup (under both privacy metrics) and for the MDS setup under the mutual information metric, our rate-privacy trade-offs are the first in the literature, to the best of our knowledge.

Abstract

We present a hypergraph coloring based approach to pliable index coding (PICOD). We represent the given PICOD problem using a hypergraph consisting of m messages as vertices and the request-sets of the n clients as hyperedges. A conflict- free coloring of a hypergraph is an assignment of colors to its vertices so that each hyperedge contains a uniquely colored vertex. We show that various parameters arising out of conflict- free colorings (and some new variants) of the PICOD hypergraph result in new upper bounds for the optimal PICOD length. Using these new upper bounds, we show the existence of single-request PICOD schemes with length O(log2 Γ), where Γ is the maximum number of hyperedges overlapping with any hyperedge. For the t-request PICOD scenario, we show the existence of PICOD schemes of length max(O(log Γ log m), O(t log m)), under some mild conditions on the graph parameters. These results improve upon earlier work in general. We also show that our achievable lengths in the t-request case are asymptotically optimal, up to a multiplicative factor of log t. Our existence results are accompanied by randomized constructive algorithms, which have complexity polynomial in the parameters of the PICOD problem, in expectation or with high probability. Index Terms--Index Coding, Pliabl