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.
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.
We study relationships between worst-case and random-noise properties of error correcting codes. More concretely, we consider connections between minimum distance, list decoding radius, and block error probability on noisy channels. A recent result of Pernice, Sprumont, and Wootters established the tight connection between list decoding radius and symmetric channel performance for linear codes. We extend this result to general codes. The proof proceeds by directly bounding the weight distribution rather than by sharp threshold techniques. We then turn to the relation between minimum distance and symmetric channel performance. The results we just described imply that a q-ary code of relative distance δ has vanishing error probability on the symmetric channel up to the Johnson radius Jq(δ). We improve upon this bound in the case of linear codes, for a range δ, for q≥4. In our proof we consider the \emph{erasure} properties of codes, and bound their weight distribution through inequalities introduced by Samorodnitsky. The latter part of the proof gives a more general technique that bounds the symmetric channel performance of a linear code with constant relative distance and good erasure channel performance.
Low-density parity-check (LDPC) codes have been one of the most popular error correction candidates in modern communication and data storage systems for the past three decades due to their capacity-approaching error correction capability under the Belief Propagation (BP) decoding algorithms. In this dissertation, we investigate three topics related to efficient and effective decoding algorithms and the code design of LDPC codes. In the first part of this dissertation, we propose a methodology with the help of artificial intelligence to design Finite Alphabet Iterative Decoders (FAID) for LDPC codes, which are not only of great theoretical but also practical importance. This model-driven neural network (NN) framework unfolds the decoding iterations, introduces quantized neural networks (QNN) to model the FAIDs, and proposes a new cost function, namely, bit error rate (BER), to address the inefficiency in discrete-output channel scenarios. The low precision activations in the QNN and quantization in the cost functions cause a critical issue that their gradients vanish almost everywhere, making it difficult to use classical backward propagation. We design and leverage straight-through estimators as surrogate gradients to tackle this issue and provide a joint training scheme. These QNN-aided FAIDs, are capable of surpassing the floating-point BP algorithms, with much lower complexity and faster convergence. The QNN-aided approach is general, as it can be applied to both continuous and discrete-output channels. In the second part of this dissertation, we propose a new code construction of LDPC codes based on the conventional parity-check matrices of Reed-Solomon (RS) codes. We investigate the girth and cycle structure and introduce an efficient searching algorithm to reduce short cycles in their Tanner graphs and to construct LDPC codes with a girth of at least eight. We use masking to further reduce the number of short cycles and to adjust the column and row weights of the parity-check matrices of the constructed codes for performance improvement. Our designs are systematic and flexible, which balance the requirements of good waterfall performance and low error-floor while maintaining a structure that facilitates implementation. In the third part of this dissertation, we investigate binary quasi-cyclic (QC) LDPC codes and their capability to correct phased bursts of erasures. We prove that the peeling algorithm when applied to such parity-check matrices of column weight two can correct all erasures that can be corrected by a maximum likelihood (ML) decoder. We show that by modifying the parity-check matrices of column weight two and globally coupling them, the erasure correcting capability can be further enhanced. For the Additive White Gaussian Noise (AWGN) channel, we design QC LDPC codes with parity-check matrices of column weight three or more that can correct phased bursts of erasures and perform well over the AWGN channel. Our analysis of QC-LDPC codes with parity-check matrices of column weight two is rather comprehensive as we determine, for all such codes, their dimensions, minimum Hamming distances, and their capabilities to correct phased bursts.
Quantum information processing (QIP) studies the representation, manipulation, and transmission of information using quantum systems. By leveraging counterintuitive quantum phenomena such as superposition and entanglement, QIP enables new paradigms for computation, communication, and learning that can surpass classical limits in certain regimes. Foundational tasks in QIP include quantum data compression, quantum communication, and quantum learning and optimization, which together form the basis for scalable quantum technologies. This thesis develops new frameworks and algorithms at the intersection of quantum information theory, quantum learning, and quantum-inspired modeling. The thesis is organized into three parts. The first part studies quantum compression problems; the second addresses quantum communication; and the third develops quantum learning and optimization frameworks with applications to complex systems. In the first part, a new formulation for lossy quantum-classical source coding, termed rate-channel theory, is introduced, replacing the conventional distortion-based formulation with a posterior-channel-based framework under a block-error criterion. The framework is further generalized to incorporate quantum side information at the decoder. A connection between rate-channel theory and classical rate-distortion theory is also established, showing that optimal rate-distortion performance can be recovered under suitable conditions. These results provide a unified and flexible framework for data compression, which is essential for scalable quantum computing infrastructure, enabling efficient storage of quantum data, such as outputs from quantum sensors (e.g., MRI) and information encoded in photonic systems for satellite and optical communication. In the second part, the problem of computing functions of distributed sources over classical-quantum multiple access channels is studied. A new coding framework is developed that combines algebraic structured codes with unstructured random coding techniques, enabling efficient communication of functions without reconstructing individual sources. The resulting achievable conditions, expressed in terms of single-letter quantum information quantities, strictly enlarge the class of sources for which reliable computation is possible. These results contribute to the theoretical foundations of quantum network communication and are directly relevant to deep-space satellite-based quantum communication, distributed quantum computing, and the design of scalable quantum network infrastructures. In the final part, new approaches to quantum learning and optimization are developed. A geometry-aware quantum optimization framework is proposed based on a novel quantum information metric and an unbiased estimator constructed from single-shot measurements. This leads to an optimization method with constant sample complexity per iteration and provable exponential convergence under mild conditions, while avoiding saddle points and local minima. Such advances are particularly relevant for challenging optimization tasks in quantum sensing and quantum computational modeling of many-body systems. Building on this optimization framework, a Hamiltonian learning approach is introduced to infer interaction structures from time-resolved measurement data, with finite-sample guarantees and polynomial scaling with system size. This framework is further extended to develop a quantum-inspired generative model for gene regulatory network inference, where interactions are encoded as a parameterized Hamiltonian evolving over pseudotime. The proposed methods demonstrate strong performance on synthetic benchmarks and reveal biologically meaningful structures in real-world data, with applications to multi-omics integration, cancer genomics, and systems biology. Overall, this thesis advances the theoretical and algorithmic foundations of quantum information processing, with contributions spanning compression, communication, and learning. These developments support the design of resource-efficient and scalable quantum technologies, enabling applications in quantum sensing, quantum networks, distributed quantum computation, and the modeling of complex physical and biological systems.
In the first part of this thesis we are interested in the asymptotic performance analysis of Non-Binary Low-Density Parity-Check (NBLDPC) codes over the Binary Erasure Channel (BEC) decoded via the suboptimal Belief Propagation (BP) decoder as well as the optimal Maximum-A-Posteriori (MAP) decoder. Previously, NBLDPC codes defined with respect to a finite field have been studied in the literature. Unfortunately, for these codes the asymptotic analysis of the BP decoder in terms of density evolution is cumbersome since the involved densities "live" in a high dimensional space. To alleviate this problem, we introduce ensembles defined with respect to the general linear group. For these ensembles the density evolution equations can be written in a compact form. We compute thresholds for different alphabet sizes for various NBLDPC ensembles. Surprisingly, the threshold is not a monotonic function of the alphabet size. We also conjecture the stability condition for NBLDPC ensembles defined with respect to finite fields over any binary memoryless symmetric channel. We then consider the performance of NBLDPC codes under MAP decoding when transmission takes place over the BEC. Towards this goal, we generalize the concepts of the peeling decoder and stopping sets to NBLDPC codes. Using these concepts, we give a combinatorial characterization of decoding failures for NBLDPC codes decoded via the BP decoder. We use the decoding failure criterion and the density evolution analysis to compute the asymptotic residual degree distribution for NBLDPC codes. The rate of this residual ensemble gives the conditional entropy of the NBLDPC code. To compute the rate of the residual ensemble we generalize the criterion of [1] to the non-binary setting, which, when satisfied, guarantees that almost every code in the ensemble has a rate equal to the design rate. We observe that the Maxwell construction of [1], relating the performance of MAP and BP decoding via the Extended BP GEXIT (EBP GEXIT [2]) function, holds in the setting of NBLDPC codes. The weight and stopping set distribution of a code are related to its performance under the MAP and the BP decoder respectively. We first concentrate on the weight distribution of regular NBLDPC ensembles. We derive the average weight distribution of regular NBLDPC ensembles. Using this, we derive the average of equivalent binary weight distribution of regular NBLDPC ensembles. We show that as the alphabet size becomes larger the equivalent binary weight distribution converges to the weight distribution of Gallager's random parity check ensemble. The average weight distribution of binary LDPC ensembles has been extensively studied in the literature. Much less is known about the probability distribution of this quantity. In particular, the question of the concentration of the weight distribution around the ensemble average has not been addressed. We compute the variance of the weight distribution of binary regular LDPC ensembles. Using this and the second moment method we obtain bounds on the probability that a randomly chosen code has its weight distribution close to the ensemble average. We show that a large fraction of the total number of codes have their weight distribution close to the average. We apply the same technique for the stopping set distribution of binary regular LDPC ensembles. Again we show that a large fraction of total number of codes have their stopping set distribution close to the ensemble average. In the last part of this thesis we address the question of the existence of the EBP GEXIT function. The EBP GEXIT function plays a fundamental role in the asymptotic analysis of sparse graph codes. For transmission over the BEC using binary LDPC codes, the analytic properties of the EBP GEXIT function are relatively simple and well understood. The case of general BMS channel is much harder and even the existence of the curve is not known in general. We introduce some tools from non-linear analysis which can be useful to prove the existence of EXIT like curves in some cases. The main tool is the Krasnoselskii-Rabinowitz (KR) bifurcation theorem.
With the development of communication technology, modern communication networks need to achieve ultra-high reliability to meet practical demands. Forward error correction coding has been widely used in real-world communication systems for providing reliable data transmission over noisy channels. In this thesis, we investigate the efficient performance evaluation methods for block codes over memoryless channels. Performance bounds are powerful tools to provide insights on the error performance of the coded systems. In many practical scenarios where performance bounds are not applicable (e.g., due to the unavailability of the relevant coding parameters under a given decoder), the Monte Carlo simulation is still popular despite its inefficiency, especially in the low error probability regime. As a variance-reduction technique, importance sampling (IS) can significantly reduce the sample size needed for reliable estimation. We firstly examine the problem of efficient performance evaluation of linear block codes over binary symmetric channels (BSCs). Contrary to the conventional wisdom, we prove that for BSCs, all bounds based on Gallager’s first bounding technique, including the famous union bound, are not asymptotically tight for all possible choices of the Gallager region. By proposing the so-called input demodulated-output weight enumerating function (IDWEF) of a code, asymptotically tight maximum-likelihood decoding upper and lower bounds for BSCs are derived. For the cases that coding parameters are absent or suboptimal decoders are applied, we propose an efficient IS estimator by deriving the optimal IS distribution of the Hamming weight of the error vector. In addition, the asymptotic percentage saving of the proposed IS estimator over the state-of-the-art IS estimator is characterized in terms of the sample size. Its accuracy in predicting the efficiency of the proposed IS estimator is verified by extensive computer simulation. We further examine the IS estimator design and efficiency analysis problems for the additive white generalized Gaussian noise (AWGGN) channel. The generalized Gaussian distribution is an effective model to describe real-world systems with impulsive noise. It can be specialized to the Laplace and Gaussian distributions depending on the choices of the decay rates of the heavy tail. By deriving the optimal IS distribution on the one-dimensional space mapped from the observation space, we present a general framework for designing IS estimators for linear block codes over a memoryless continuous channel. We apply the framework to the AWGGN channel and propose a noise-magnitude-domain IS (NM-IS) estimator. As an efficiency measure, the asymptotic IS gain of the proposed estimator is derived in a multiple integral as the signal-to-noise ratio (SNR) tends to infinity. Specifically, we reduce the gains of both Laplace and Gaussian noise cases to a one-dimensional integral. In addition, by limiting the use of the union bound to an L1-norm sphere with an optimized radius, we derive the sphere bound for the additive white Laplace noise channel. Simulation results show the efficiency of the proposed IS estimator in terms of the sample size and verify the accuracy of the prediction of the derived IS gain. Besides, we specialize the proposed framework to further improve the efficiency of the IS simulation based on the side information of the modulation. For the AWGGN channel with binary phase-shift keying (BPSK) modulation, we propose an enhanced NM-IS estimator, which outperforms the NM-IS estimator in efficiency. For the additive white Gaussian noise channel with M-PSK modulation, we propose an angular domain IS estimator and provide its efficiency analysis in terms of the asymptotic IS gain. Furthermore, in the performance evaluation of communication systems, it is often seen that researchers are more interested in the required SNR at a target error probability Pe than the other way around. The conventional solution to this Pe-targeted SNR estimation problem involves interpolation of simulated error probabilities at multiple handpicked SNRs for estimating the required SNR at the target error probability. We propose a Pe-targeted iterative IS estimator that solves the problem algorithmically. The proposed method can achieve the same efficiency (in terms of sample size) as estimating the error probability at the required SNR and allow the confidence interval of the SNR estimate to be obtained.
We present lower bounds on the bit error probability of binary linear block codes, and on the gap between the channel capacity and the rate of these codes for which reliable communica- tion is achievable. The results are valid for memo- ryless binary-input output-symmetric (MBIOS) chan- nels. The lower bounds provide a quantitative mea- sure for the number of cycles of bipartite graphs which represent good error-correcting codes. The tightness of the lower bounds is especially pronounced for the binary erasure channel (BEC); to this end, we analyze a sequence of ensembles of low-density parity-check (LDPC) codes which closely approach these bounds. I. Introduction If a linear block code can be represented by a cycle-free fac- tor graph which only includes variable nodes and parity-check nodes, then maximum-likelihood soft decision decoding can be performed with low complexity (1). Theorem 5 in (1) indicates that these graphs represent codes with very poor minimum distance. The bounds in (1) only refer to the minimum dis- tance of cycle-free codes, and in this work we derive lower bounds on the bit error probability and the gap to capacity for codes on graphs which are represented by bipartite graphs (with or without cycles). We derive in this work information- theoretic lower bounds on the bit error probability of a binary linear code used over MBIOS channels. The bounds are ex- pressed in terms of the density of an arbitrary parity-check matrix which represents the binary linear code (i.e., the num- ber of ones in the matrix normalized per information bit), and they are valid for codes whose bipartite graphs are with or without cycles. We introduce a quantitative measure for the cycles in a bipartite graph which represents a binary lin- ear code (where the graph only includes variable nodes and parity-check nodes). The bounds provide an interpretation for the tradeofi which exists between the bit error proba- bility and gap to capacity of an arbitrary LDPC code (i.e., its performance limitations), and the density of an arbitrary parity-check matrix which represents the code (where the lat- ter afiects the decoding complexity per information bit and per iteration, under a message-passing iterative decoding al- gorithm). We present in this work quantitative results which indicate that in order to approach the channel capacity with vanishing bit error probability, LDPC codes should not have too sparse parity-check matrices, as otherwise their inherent gap to capacity becomes large. In fact, we show that the density of any parity-check matrix and the fundamental num- ber of cycles of the graph which represents the code should increase at least like log 1 where designates the gap to ca- pacity under iterative message-passing decoding (see (2), (3)). The tightness of the lower bounds which are derived in this work (and whose validity is for any sequence of codes with 1 1.5 2 2.5 3 3.5 4 4.5