Structural Conditions for Performance Guarantees in Coding Theory and Learning

Abstract

This dissertation investigates how structural properties of information-processing systems govern their performance in communication and learning tasks. In the first part, we develop new tools in coding and information theory. We study channel comparison problems and introduce a quantitative refinement of the classical notion of \emph{more capable} channels, termed \emph{more capable with advantage}. We prove tensorization properties, characterize the comparison between the binary symmetric channel (BSC) and binary erasure channel (BEC), and apply the framework to obtain new list-decoding guarantees and improved lower bounds on the entropy rate of binary hidden Markov processes. Then, we investigate the relationship between worst-case and random-noise properties of error-correcting codes. In particular, we establish new connections between minimum distance, list-decoding radius, weight distributions, and performance on symmetric channels. Our results extend recent characterizations of the interplay between list decoding capacity and channel capacity from linear codes to arbitrary codes, and provide improved bounds for linear codes through the analysis of erasure-channel behavior and Samorodnitsky's inequalities. The second part of the dissertation examines analogous questions in learning theory through the lens of neural networks. We study the learnability of high-degree parity functions, a classical benchmark for understanding the computational limits of learning algorithms. We show that for gradient descent on regular neural networks, learnability depends critically on the initial distribution of the parameters. While discrete Rademacher initialization enables efficient learning of almost-full parities, sufficiently large Gaussian perturbations prevent learning. These results reveal a sharp dependence of optimization dynamics on initialization. The analysis introduces gradient-alignment (GAL), a loss-dependent measure, that quantifies how the choice of initialization could affects the learnability of a target function. Taken together, the results of this dissertation demonstrate that quantitative structural information—whether encoded in channel orderings, code weight distributions, or neural-network initializations—can fundamentally determine the boundary between success and failure in information processing tasks.