Due to the fundamental connection between next-symbol prediction and compression, modern predictive models, such as large language models (LLMs), can be combined with entropy coding to achieve compression rates that surpass those of standard compression algorithms. However, this approach relies on the assumption that the predictive model produces identical output distributions at both the encoder and decoder, since even small mismatches can cause the decoding to fail. This assumption often fails with complex predictive models, particularly those based on neural networks, a phenomenon referred to as non-determinism. In this work, we propose a new compression algorithm based on next-token prediction that is robust to arbitrarily large, but structured, prediction mismatches. We prove the correctness of the proposed scheme under a formal mismatch certification, characterize its theoretical performance, and validate it experimentally on real datasets. Our results demonstrate reliable operation within the certified mismatch regime while achieving compression ratios that exceed those of commonly used compression methods.

We examine the capacity for the multinomial channel, a natural extension of the binomial channel. In the multinomial channel setting, the input is a probability distribution over$k$entries, and the output of the channel is$n$items sampled independently with the chosen input probability distribution. Applications of this channel include the use of composite DNA, which is a method for expanding the alphabet set used in DNA storage systems in order to improve the information throughput. In this work, we compute non-asymptotic upper and lower bounds for the information rate of the multinomial channel.

We establish the capacity of a class of communication channels introduced by Makur. The$n$-letter input from a finite alphabet is passed through a discrete memoryless channel$P_{Z|X}$and then the output$n$-letter sequence is uniformly permuted. We show that the maximal communication rate (normalized by$\log n$) equals${\frac{1}{ 2}} ( \textsf {rank}(P_{Z|X})-1)$whenever$P_{Z|X}$is strictly positive. This is done by establishing a converse bound matching the achievability of Makur. The two main ingredients of our proof are: 1) a sharp bound on the Kullback-Leibler divergence of a uniformly sampled vector from a type class and observed through a DMC to an iid vector; and 2) the covering$\varepsilon $-net of a probability simplex with Kullback-Leibler divergence as a metric. In addition to strictly positive DMC we also find the noisy permutation capacity for$q$-ary erasure channels, the Z-channel and others.

This paper considers the problem of finding a tighter upper bound on the minimax regret of patterns, a class used to study large-alphabet distributions which avoids infinite asymptotic regret and redundancy. Our method for finding upper bounds for minimax regret uses cover numbers with Kullback-Leibler (KL) divergence as the distance. Compared to existing results by Acharya et al. (2013), we are able to improve the power of the exponent on the logarithmic term, giving a minimax regret bound which matches the best known minimax redundancy bound on patterns.

We study the potential of data-driven deep learning methods for separation of two communication signals from an observation of their mixture. In particular, we assume knowledge on the generation process of one of the signals, dubbed signal of interest (SOI), and no knowledge on the generation process of the second signal, referred to as interference. This form of the single-channel source separation problem is also referred to as interference rejection. We show that capturing high-resolution temporal structures (nonstationarities), which enables accurate synchronization to both the SOI and the interference, leads to substantial performance gains. With this key insight, we propose a domain-informed neural network (NN) design that is able to improve upon both “off-the-shelf” NNs and classical detection and interference rejection methods, as demonstrated in our simulations. Our findings highlight the key role communication-specific domain knowledge plays in the development of data-driven approaches that hold the promise of unprecedented gains.

A number of engineering and scientific problems require representing and manipulating probability distributions over large alphabets, which we may think of as long vectors of reals summing to 1. In some cases it is required to represent such a vector with only b bits per entry. A natural choice is to partition the interval [0,1] into 2buniform bins and quantize entries to each bin independently. We show that a minor modification of this procedure – applying an entrywise non-linear function (compander) f(x) prior to quantization – yields an extremely effective quantization method. For example, for b = 8(16) and 105-sized alphabets, the quality of representation improves from a loss (under KL divergence) of 0.5(0.1) bits/entry to 10−4(10−9) bits/entry. Compared to floating point representations, our compander method improves the loss from 10−1(10−6) to 10−4(10−9) bits/entry. These numbers hold for both real-world data (word frequencies in books and DNA k-mer counts) and for synthetic randomly generated distributions. Theoretically, we set up a minimax optimality criterion and show that the compander $f(x) \propto \operatorname{ArcSinh} (\sqrt {(1/2)(K\log K)x} )$ achieves near-optimal performance, attaining a KL-quantization loss of ≍ 2−2blog2K for a K-letter alphabet and b →∞. Interestingly, a similar minimax criterion for the quadratic loss on the hypercube shows optimality of the standard uniform quantizer. This suggests that the ArcSinh quantizer is as fundamental for KL-distortion as the uniform quantizer for quadratic distortion.

We establish the capacity of a class of communication channels introduced in [2]. The n-letter input from a finite alphabet is passed through a discrete memoryless channel PZ|Xand then the output n-letter sequence is uniformly permuted. We show that the maximal communication rate (normalized by log n) equals $\frac{1}{2}\left( {\operatorname{rank} \left( {{P_{Z\mid X}}} \right) - 1} \right)$ whenever PZ|Xis strictly positive. This is done by establishing a converse bound matching the achievability of [2]. The two main ingredients of our proof are (1) a sharp bound on the entropy of a uniformly sampled vector from a type class and observed through a DMC; and (2) the covering ε-net of a probability simplex with Kullback-Leibler divergence as a metric. In addition to strictly positive DMC we also find the noisy permutation capacity for q-ary erasure channels, the Z-channel and others.

Consider the problem of representing a distribution$\pi$on a large alphabet of size$k$up to fidelity$\varepsilon$in Kullback-Leibler (KL) divergence. Heuristically, arguing as for quadratic loss in high dimension, one expects that about$(k/2)\log(1/\varepsilon)$bits would be required. We show this intuition is correct by proving explicit non-asymptotic bounds for the minimal average distortion when$\pi$is randomly sampled from a symmetric Dirichlet prior on the simplex. Our method is to reduce the single-sample problem to the traditional setting of iid samples, but for a non-standard rate distortion question with the novel distortion measure$d(x, y)= x\log(x/y)$, which we call divergence distortion. Practically, our results advocate using a$x\mapsto x^{2/3}$compander (for small$x$) followed by a uniform scalar quantizer for storing large-alphabet distributions.

Enabling Lidar systems to detect objects at very long ranges has the potential to be extremely valuable for autonomous driving applications, but is challenging due to noise. In this work, we leverage information from multiple consecutive frames to improve the detection capabilities of Lidar systems. We develop a mathematical model whose solution gives a low memory and low computation algorithm that detects some fraction of the objects present while keeping the number of false positives small. Performance of the proposed method is characterized using simulations of a realistic Lidar chain.

This paper addresses the problem of adding redundancy to a collection of physical objects so that the overall system is more robust to failures. In contrast to its information counterpart, which can exploit parity to protect multiple information symbols from a single erasure, physical redundancy can only be realized through duplication and substitution of objects. We propose a bipartite graph model for designing defect-tolerant systems, in which the defective objects are replaced by the judiciously connected redundant objects. The fundamental limits of this model are characterized under various asymptotic settings and both asymptotic and finite-size systems that approach these limits are constructed. Among other results, we show that the simple modular redundancy is in general suboptimal. As we develop, this combinatorial problem of defect tolerant system design has a natural interpretation as one of graph coloring, and the analysis is significantly different from that traditionally used in information redundancy for error-control codes.

This paper addresses the question of how to add redundancy to a collection of physical objects so that the overall system is more robust to failures. Physical redundancy can (generally) only be achieved by employing copy/substitute procedures. This is fundamentally different from information redundancy, where a single parity check simultaneously protects a large number of data bits against a single erasure. We propose a bipartite graph model of designing defect-tolerant systems where defective objects are repaired by reconnecting them to strategically placed redundant objects. The fundamental limits of this model are characterized under various asymptotic settings and both asymptotic and finite-size optimal systems are constructed. Mathematically, we say that a k by m bipartite graph corrects t defects over alphabet of size q if for every q-coloring of k left vertices there exists a coloring of m right vertices such that every left vertex is connected to at least t same-colored right vertices. We study the tradeoff between redundancy m/k and the total number of edges in the graph divided by k. The question is trivial when q ≥ k: the optimal solution is a simple t-fold replication. However, when q <; k some non-trivial savings are possible by leveraging the inherent repetition of colors.