Applications of Linear Programming to Coding Theory

Maximum-likelihood decoding is often the optimal decoding rule one can use, but it is very costly to implement in a general setting. Much effort has therefore been dedicated to find efficient decoding algorithms that either achieve or approximate the error-correcting performance of the maximum-likelihood decoder. This dissertation examines two approaches to this problem. In 2003 Feldman and his collaborators defined the linear programming decoder, which operates by solving a linear programming relaxation of the maximum-likelihood decoding problem. As with many modern decoding algorithms, is possible for the linear programming decoder to output vectors that do not correspond to codewords; such vectors are known as pseudocodewords. In this work, we completely classify the set of linear programming pseudocodewords for the family of cycle codes. For the case of the binary symmetric channel, another approximation of maximum-likelihood decoding was introduced by Omura in 1972. This decoder employs an iterative algorithm whose behavior closely mimics that of the simplex algorithm. We generalize Omura's decoder to operate on any binary-input memoryless channel, thus obtaining a soft-decision decoding algorithm. Further, we prove that the probability of the generalized algorithm returning the maximum-likelihood codeword approaches 1 as the number of iterations goes to infinity.

Model complexity affects transient population dynamics following a dispersal event: A case study with pea aphids

Stage-structured population models predict transient population dynamics if the population deviates from the stable stage distribution. Ecologists’ interest in transient dynamics is growing because populations regularly deviate from the stable stage distribution, which can lead to transient dynamics that differ significantly from the stable stage dynamics. Because the structure of a population matrix (i.e., the number of life-history stages) can influence the predicted scale of the deviation, we explored the effect of matrix size on predicted transient dynamics and the resulting amplification of population size. First, we experimentally measured the transition rates between the different life-history stages and the adult fecundity and survival of the aphid, Acythosiphon pisum. Second, we used these data to parameterize models with different numbers of stages. Third, we compared model predictions with empirically measured transient population growth following the introduction of a single adult aphid. We find that the models with the largest number of life-history stages predicted the largest transient population growth rates, but in all models there was a considerable discrepancy between predicted and empirically measured transient peaks and a dramatic underestimation of final population sizes. For instance, the mean population size after 20 days was 2394 aphids compared to the highest predicted population size of 531 aphids; the predicted asymptotic growth rate (λmax) was consistent with the experiments. Possible explanations for this discrepancy are discussed. Includes 4 supplemental files.