Resource-constrained Coding for Communication and Computation Applications

Passcode: 0000

Abstract: Many modern applications pose new challenges and constraints on various aspects of the long-standing field of coding theory. For example, the problem of crowdsourced labeling can be modeled as a coding problem where the generator matrices must be sparse. To address this, in this dissertation, we propose coding schemes, inspired by the polar codes, that enjoy several properties including low encoding and decoding complexity, fast decay in error rate, and state-of-the-art upper bounds on the generator matrix sparsity.

The thesis then focuses on the problem of finding channel codes with large minimum distances. The large-minimum distance regime is of both theoretical and practical interests, as the transmission of information in many extreme conditions requires coding schemes that are highly robust with small or moderate rate.  We present a novel construction of cyclic codes which leads to lower bounds on the maximal size of codes in the targeted regime. Upper bounds that are stricter than prior literature are also established.

The third part of the thesis discusses the one-shot group coding problem over the classical and classical-quantum channels. In the achievability part, we introduce a new distribution that incorporates the encoding homomorphism and the underlying channel law, and characterize the performance in terms of a single-letter relative-entropy type quantity. In the converse part, we establish bounds by leveraging a hypothesis testing-based approach.

Co-Chairs: Professor Hessam Mahdavifar and Professor S. Sandeep Pradhan