Abstract

The problem of recovering from qubit erasures has recently gained attention as erasures occur in many physical systems such as photonic systems, trapped ions, superconducting qubits and circuit quantum electrodynamics. While several linear-time decoders for error correction are known, their errorcorrecting capability is limited to half the minimum distance of the code, whereas erasure correction allows one to go beyond this limit. As in the classical case, stopping sets pose a major challenge in designing efficient erasure decoders for quantum LDPC codes. In this paper, we show through simulation, that an attractive alternative here, is the use of quantum expander codes in conjunction with the peeling decoder that has linear complexity. We also discuss additional techniques including small-set-flip decoding, that can be applied following the peeling operation, to improve decoding performance and their associated complexity.

Abstract

Dual discriminator generative adversarial networks (D2 GANs) were introduced to mitigate the problem of mode collapse in generative adversarial networks. In D2 GANs, two discriminators are employed alongside a generator: one discriminator rewards high scores for samples from the true data distribution, while the other favors samples from the generator. In this work, we first introduce {dual discriminator α-GANs (D2 α-GANs)}, which combines the strengths of dual discriminators with the flexibility of a tunable loss function, α-loss. We further generalize this approach to arbitrary functions defined on positive reals, leading to a broader class of models we refer to as generalized dual discriminator generative adversarial networks. For each of these proposed models, we provide theoretical analysis and show that the associated min-max optimization reduces to the minimization of a linear combination of an f-divergence and a {reverse} f-divergence. This generalizes the known simplification for D2-GANs, where the objective reduces to a linear combination of the KL-divergence and the reverse KL-divergence. Finally, we perform experiments on 2D synthetic data and use multiple performance metrics to capture various advantages of our GANs.

Abstract

We consider a distributed multi-user secret sharing setting consisting of a dealer, n storage nodes and m secrets where each user demands a t-subset of m secrets. The user downloads shares from the storage nodes based on the designed access structure and reconstructs its secrets. Earlier work in this setting dealt with the case of t = 1; in this work, we generalize it to natural numbers. We identify a necessary condition on the access structures to ensure weak secrecy. We also make a connection between the access structures for this problem and t-disjunct matrices. We apply various t-disjunct matrix constructions in this setting and compare their performance in terms of the number of storage nodes and communication complexity. We also derive bounds on the optimal communication complexity of a distributed secret sharing protocol. Finally, we characterize the capacity region of the DMUSS problem when the access structure is specified

Abstract

A code of length n is said to be (combinatorially) (ρ, L)-list decodable if the Hamming ball of radius ρn around any vector in the ambient space does not contain more than L codewords. We study a recently introduced class of higher order MDS codes, which are closely related (via duality) to codes that achieve a generalized Singleton bound for list decodability. For some ℓ ≥ 1, higher order MDS codes of length n, dimension k, and order ℓ are denoted as (n, k)-MDS(ℓ) codes. We present a number of results on the structure of these codes, identifying the ‘extend-ability’ of their parameters in various scenarios. Specifically, for some parameter regimes, we identify conditions under which (n1, k1)-MDS(ℓ1) codes can be obtained from (n2, k2)-MDS(ℓ2) codes, via various techniques. We believe that these results will aid in efficient constructions of higher order MDS codes. We also obtain a new field size upper bound for the existence of such codes, which arguably improves over the best known existing bound, in some parameter regimes. Due to space restrictions, the full version of this paper containing proofs of claims is made available in [1].

Abstract

Blockchains have proven to provide a high level of performance in terms of security and reliability for various applications like cryptocurrencies and Internet-of-Things (IoT). Prism is a recent blockchain algorithm that achieves the physical limit on throughput and latency without compromising security. In recent days, reinforcement learning approaches are investi- gated in traditional blockchains, to improve performance. In this work, we apply Deep Reinforcement Learning (DRL) to one of the promising blockchain protocols, Prism, to optimize its performance. We propose a Deep Reinforcement Learning- based Prism Blockchain (DRLPB) scheme which dynamically optimizes the parameters of the Prism blockchain and helps in achieving a better performance. In DRLPB, we apply two widely used DRL algorithms, Dueling Deep Q Networks (DDQN) and Proximal Policy Optimization (PPO). This work presents a novel approach to applying DDQN and PPO to a blockchain protocol and comparing the performance. The DRLPB scheme adapts the Prism blockchain parameters to enhance the number of votes upto 84% more than Prism, while still preserving the security and latency performance guarantees of Prism.

Abstract

Maximally recoverable codes are a class of codes which recover from all potentially recoverable erasure patterns given the locality constraints of the code. In earlier works, these codes have been studied in the context of codes with locality. The notion of locality has been extended to hierarchical locality, which allows for locality to gradually increase in levels with the increase in the number of erasures. We consider the locality constraints imposed by codes with two-level hierarchical locality and define maximally recoverable codes with data-local and local hierarchical locality. We derive certain properties related to their punctured codes and minimum distance. We give a procedure to construct hierarchical data-local MRCs from hierarchical local MRCs. We provide a construction of hierarchical local MRCs for all parameters. We also give constructions of MRC with hierarchical locality for some parameters, whose field size is smaller than that of known constructions for general parameters. We also derive a field size lower bound on MRC with hierarchical locality.

Abstract

We consider a generalization of the recently proposed gradient coding framework where a large dataset is divided across n workers and each worker transmits to a master node one or more linear combinations of the gradients over the data subsets assigned to it. Unlike the conventional framework which requires the master node to recover the sum of the gradients over all the data subsets in the presence of s straggler workers, we relax the goal of the master node to computing the sum of at least some α fraction of the gradients. The broad goal of our work is to study the optimal computation and communication load per worker for this approximate gradient coding framework. We begin by deriving a lower bound on the computation load of any feasible scheme and also propose a strategy which achieves this lower bound, albeit at the cost of high communication load and a number of data partitions which can be polynomial in the number of workers n. We then restrict attention to schemes which utilize a number of data partitions equal to n and propose schemes based on cyclic assignment which have a lower communication load. When each worker transmits a single linear combination, we also prove lower bounds on the computation load of any scheme using n data partitions.

Abstract

Codes with locality allow for efficient recovery from single node failures by minimizing the number of nodes accessed to repair a failed node. These codes can also be extended to handle multiple erasures. Codes with hierarchical locality are another extension of codes with locality, which offer multiple levels of locality as the number of erasures increase. Maximally recoverable codes (MRC) are a class of codes, which satisfy the locality property and in addition also recover from all information theoretically recoverable erasure patterns. In this work, we construct MRC with hierarchical locality based on generator matrices of linearized Reed-Solomon codes and the field size is better than the earlier known construction. We also give a random construction of MRC with hierarchical locality and characterize the field size required. Finally, we present sparse generator matrices for MRC with locality and also sparse and balanced generator matrices for MRC with locality parameter 2 for large set of parameters.

Abstract

Product codes are a class of codes which have generator matrices as the tensor product of the component codes and the codeword itself can be represented as an (m × n) array, where the component codes themselves are referred to as the row and column codes. Maximally recoverable product codes (MRPCs) are a class of codes which can recover from all information theoretically recoverable erasure patterns, given the a column and b row constraints imposed by the code. In this work, we derive puncturing and shortening properties of maximally recoverable product codes. We give a sufficient condition to characterize a certain subclass of erasure patterns as correctable and another necessary condition to characterize another subclass of erasure patterns as not correctable. In an earlier work, higher order MDS codes denoted by MDS(l) have been defined in terms of generic matrices and these codes have been shown to be constituent row codes for maximally recoverable product codes for the case of a = 1. We derive a certain inclusion-exclusion type principle for characterizing the dimension of intersection spaces of generic matrices. Applying this, we formally derive a relation between MDS(3) codes and points/lines of the associated projective space.

Abstract

In distributed storage systems, cooperative regener- ating codes tradeoff storage for repair bandwidth in the case of multiple node failures. In rack-aware distributed storage systems, there is no cost associated with transferring symbols within a rack. Hence, the repair bandwidth will only take into account cross-rack transfer. Rack-aware regenerating codes for the case of single node failures have been studied and their repair bandwidth tradeoff characterized. In this paper, we consider the frame- work of rack-aware cooperative regenerating codes for the case of multiple node failures where the node failures are uniformly distributed among a certain number of racks. We characterize the storage repair-bandwidth tradeoff as well as derive the minimum storage and minimum repair bandwidth points of the tradeoff. We also provide explicit constructions of minimum bandwidth rack-aware cooperative regenerating codes and minimum storage rack-aware cooperative regenerating codes for a large range of parameters. We also consider another extension of minimum stor- age cooperative regenerating codes, in which we design slightly sub-optimal cooperative regenerating codes with much lower sub- packetization. -MSR codes are a class of codes introduced to tradeoff sub-packetization level for a slight increase in the repair bandwidth for the case of single node failures. We introduce the framework of -MSCR codes which allow for a similar tradeoff for the case of multiple node failures. We present a construction of -MSCR codes, which can recover from two node failures, by concatenating a class of MSCR codes and scalar linear codes. We give a repair procedure to repair the -MSCR codes in the event of two node failures and calculate the repair bandwidth for the same. We characterize the increase in repair bandwidth incurred by the method in comparison with the optimal repair bandwidth. Finally, we show the subpacketization level of -MSCR codes scales logarithmically in the number of nodes.