We study the problem of transmission of information over classical-quantum (CQ) channels in the one-shot regime where the underlying codes are constrained to be shiftedgroup codes. Given a groupG, a group code of lengthnis a subgroup ofGn. In the achievability part, we introduce a new collection of input probability distributions that incorporates the encoding homomorphism and the underlying channel law. Using a random coding argument, we characterize the performance of group codes in terms of hypothesis testing relative-entropic quantities. In the converse part, we establish bounds by leveraging a hypothesis testing-based approach. Furthermore, we apply the one-shot result to the asymptotic stationary memoryless setting, and establish a single-letter lower bound on thegroup capacityof a CQ channel. Moreover, we derive a matching upper bound on the asymptotic group capacity.

We study the one-shot channel coding problem over classical and classical-quantum channels, where the underlying codes are constrained to be group codes. In the achievability part, we introduce a new distribution that incorporates the encoding homomorphism and the underlying channel law. Using a random coding argument, we characterize the performance in terms of hypothesis testing relative-entropies. In the converse part, we es-tablish bounds by leveraging a hypothesis testing-based approach. Further we apply the one-shot result to the asymptotic use case and establish the group capacities for both channels.

In general, the generator matrix sparsity is a critical factor in determining the encoding complexity of a linear code. Further, certain applications, e.g., distributed crowdsourcing schemes utilizing linear codes, require most or even all the columns of the generator matrix to have some degree of sparsity. In this paper, we leverage polar codes and the well-established channel polarization to design capacity-achieving codes with a certain constraint on the weights of all the columns in the generator matrix (GM) while having a low-complexity decoding algorithm. We first show that given a binary-input memoryless symmetric (BMS) channel$W$and a constant$s \in (0, 1]$, there exists a polarization kernel such that the corresponding polar code is capacity-achieving with the rate of polarization$s/2$, and the GM column weights being bounded from above by$N^{s}$. To improve the sparsity versus error rate trade-off, we devise a column-splitting algorithm and two coding schemes for BEC and then for general BMS channels. The polar-based codes generated by the two schemes inherit several fundamental properties of polar codes with the original$2 \times 2$kernel including the decay in error probability, decoding complexity, and the capacity-achieving property. Furthermore, they demonstrate the additional property that their GM column weights are bounded from above sublinearly in$N$, while the original polar codes have some column weights that are linear in$N$. In particular, for any BEC and$\beta < 0.5$, the existence of a sequence of capacity-achieving polar-based codes where all the GM column weights are bounded from above by$N^{\lambda} $with$\lambda \approx 0.585$, and with the error probability bounded by${\mathcal {O}}(2^{-N^{\beta }})$under a decoder with complexity${\mathcal {O}}(N\log N)$, is shown. The existence of similar capacity-achieving polar-based codes with the same decoding complexity is shown for any BMS channel and$\beta < 0.5$with$\lambda \approx 0.631$.

Let A(n, d) denote the maximum number of code-words in a binary code of length n and minimum Hamming distance d. Deriving upper and lower bounds on A(n, d) has been a subject for extensive research in coding theory. In this paper, we examine upper and lower bounds on A(n, d) in the high-minimum distance regime, in particular, when $d = n/2 - \Theta (\sqrt n )$. We will first provide a lower bound based on a cyclic construction for codes of length n = 2m− 1 and show that $A\left({n,d = n/2 - {2^{c - 1}}\sqrt n }\right) \geq {n^c}$, where c is an integer with 1 ⩽ c ⩽ m/2 − 1. With a Fourier-analytic view of Delsarte’s linear program, novel upper bounds on $A(n,n/2 - \sqrt n ){\text{ and }}A(n,n/2 - 2\sqrt n )$ are obtained, and, to the best of the authors’ knowledge, are the first upper bounds scaling polynomially in n for the regime with $d = n/2 - \Theta (\sqrt n )$.

In this paper we study codes with sparse generator matrices. More specifically, codes with a certain constraint on the weight of all the columns in the generator matrix are considered. The end result is the following. For any binary-input memoryless symmetric (BMS) channel and any ε> 2ε*, where ε8 = 1/6 - [5/3log4/3] ≈ 0.085, we show an explicit sequence of capacity-achieving codes with all the column weights of the generator matrix upper bounded by (log N)1+ε, where N is the code block length. The constructions are based on polar codes. Applications to crowdsourcing are also shown.

This paper models the crowdsourced labeling/classification problem as a sparsely encoded source coding problem, where each query answer, regarded as a code bit, is the XOR of a small number of labels, as source information bits. In this paper we leverage the connections between this problem and well-studied codes with sparse representations for the channel coding problem to provide querying schemes with almost optimal number of queries, each of which involving only a constant number of labels. We also extend this scenario to the case where some workers can be unresponsive. For this case, we propose querying schemes where each query involves only log n items, where n is the total number of items to be labeled. Furthermore, we consider classification of two correlated labeling systems and provide two-stage querying schemes with almost optimal number of queries each involving a constant number of labels.