We introduce and analyze a discrete soft-decision channel called the linear reliability channel (LRC) in which the soft information is the rank-ordering of the received symbol reliabilities. We prove that the LRC is an appropriate approximation to a general class of binary-input, continuous-output channels when the noise variance is high. The central feature of the LRC is that its combinatorial nature allows for an extensive mathematical analysis of the channel and its corresponding hard- and soft-decision maximum-likelihood (ML) decoders. In particular, we establish explicit error exponents for ML decoding in the LRC when using random codes under both hard- and soft-decision decoding. This analysis allows for a direct, quantitative evaluation of the relative advantage of soft-decision decoding. The discrete geometry of the LRC is distinct from that of the BSC, which is characterized by the Hamming weight, offering a new perspective on code construction for soft-decision settings.

The problem of mismatched guesswork considers the additional cost incurred by using a guessing function which is optimal for a distribution q when the random variable to be guessed is actually distributed according to a different distribution p. This problem has been well-studied from an asymptotic perspective, but there has been little work on quantifying the difference in guesswork between optimal and suboptimal strategies for a finite number of symbols. In this non-asymptotic regime, we consider a definition for mismatched guesswork which we show is equivalent to a variant of the Kendall tau permutation distance applied to optimal guessing functions for the two distributions. We use this formulation to bound the cost of guesswork under mismatch given a bound on the total variation distance between those distributions.

A notable result from analysis of Boolean functions is the Basic Invariance Principle (BIP), a quantitative nonlinear generalization of the Central Limit Theorem for multilinear polynomials. We present a generalization of the BIP for bivariate multilinear polynomials, i.e., polynomials over two n-length sequences of random variables. This bivariate invariance principle arises from an iterative application of the BIP to bound the error in replacing each of the two input sequences. In order to prove this invariance principle, we first derive a version of the BIP for random multilinear polynomials, i.e., polynomials whose coefficients are random variables. As a benchmark, we also state a naive bivariate invariance principle which treats the two input sequences as one and directly applies the BIP. Neither principle is universally stronger than the other, but we do show that for a notable class of bivariate functions, which we term separable functions, our subtler principle is exponentially tighter than the naive benchmark.

Lossless compression of datasets is a problem of significant theoretical and practical interest. It appears naturally in the task of storing, sending, or archiving large collections of information for scientific research. We can greatly improve encoding bitrate if we allow the compression of the original dataset to decompress to a permutation of the data. We prove the equivalence of dataset compression to compressing a permutation-invariant structure of the data and implement such a scheme via predictive coding. We benchmark our compression procedure against state-of-the-art compression utilities on the popular machine-learning datasets MNIST and CIFAR-10 and outperform for multiple parameter sets.