PhD Thesis Defense

As more and simpler devices join our communication networks, those networks are forced to contend with a wide range of uncertainties: the number of active communicators may be unknown and time varying, the side information that they depend on may not arrive reliably, and so on. Since these types of system-level uncertainty are not accounted for in traditional communication network models, many basic questions about how well these systems can hope to perform and how to achieve those limits in practice remain unanswered. This thesis investigates the performance of lossless or almost lossless data compression systems (also known as source codes) under a variety of types of uncertainty at the decoder. I present bounds on the performance of an almost lossless point-to-point source code in scenarios where the reconstruction by the decoder is later used to aid the description of another dependent source. I demonstrate that, even under strict efficiency and reliability constraints, point-to-point source codes are not equally powerful when the decoder outputs are used as side information to help a downstream user decode a dependent source. I show the full range of possible performances and prove that the designer of the point-to-point code can control where on the spectrum, from the least to the most helpful, the reconstruction is expected to be. I also study the performance of a random binning source code when the source reconstruction from that code is used as an input to a distributed hypothesis test. I show that random binning generates a source code whose codeword serves simultaneously as a source description and as an input to a distributed hypothesis test that seeks to determine whether the coded source is independent of or dependent on side information available to the decoder. The given random binning code can serve these dual roles without significantly worsening the source coding rate. I discuss the implications of such a hypothesis test on the statistics of the random binning code output and analyze the statistics through an alternative route that involves direct analysis of the random binning code. I also analyze the statistics of the random binning code output when the source is overcompressed.