CITC 2026

Composition Theorems for Differential Privacy via Hypothesis Testing

Yana Shkel, École Polytechnique Fédérale de Lausanne

Abstract: Differential privacy (DP) is a widely studied worst-case privacy measure which provides strong guarantees on the ability to distinguish between two neighboring databases. The classic definition of DP could be alternatively formulated as a constraint on the trade-off function of the hypothesis test employed by the adversary. This perspective not only gives powerful tools to prove composition theorems for DP mechanisms, but also motivates a recently introduced generalization of DP, known as f-DP. In this talk we overview the established literature on hypothesis testing and (f-)DP, with particular focus on composition theorems. We highlight some of our recent results which included the exact composition of mechanisms for which two DP constraints hold simultaneously. The resulting privacy region admits an exact representation as a mixture over compositions of mechanisms of heterogeneous DP guarantees, yielding a framework that naturally generalizes to the composition of mechanisms for which any number of DP constraints hold. This result is shown through a structural lemma for mixtures of binary hypothesis tests. Finally, we apply the developed methodology to approximate finite f-DP compositions.

Yana Shkel is an Assistant Professor at the École Polytechnique Fédérale de Lausanne, affiliated with the Information Processing Group in the School of Computer and Communication Sciences. She received her PhD in Electrical and Computer Engineering from the University of Wisconsin–Madison in 2014 and was a Postdoctoral Researcher at Princeton University and the University of Illinois at Urbana–Champaign before joining EPFL in 2019.

Waiting and Weighting

Frans Willems, Eindhoven University of Technology

Abstract: We give a brief introduction to two universal source coding algorithms, i.e., the Repetition-Time algorithm (W. 1989) and the Context-Tree Weighting algorithm [W., Shtarkov, and Tjalkens (1995)]. We investigate what codeword-lengths these algorithms achieve, compared to ideal codeword-lengths. However, the main focus of the lecture will be on the Context-Tree Weighting algorithm. We discuss its compression performance on text-files. We use the Context-Tree Maximizing algorithm for the extraction of models from these text-files, and discuss the storage of these models. Good compression can be achieved when using letters as basic elements. However, we can also scale up from letters to tokens. The effect on the overall compression turns out to be small, but we observed that the extracted token-model achieves a better compression than a letter-model. The Context-Tree Weighting method can be used for finding a language model, but a major drawback is that its context-length is very small.

Frans Willems is an Emeritus Professor in the Signal Processing Systems group at Eindhoven University of Technology. He received his MSc in Electrical Engineering from TU/e in 1979 and his PhD from KU Leuven, Belgium, in 1982, before returning to TU/e the same year as Assistant Professor. He is the recipient of the 2025 IEEE Richard W. Hamming Medal and the 2026 IEEE Claude E. Shannon Award.

The sample complexity of lossless data compression

Ioannis Kontoyiannis, University of Cambridge

Abstract: A new framework is introduced for examining and evaluating the fundamental limits of lossless data compression, that emphasizes genuinely non-asymptotic results. The sample complexity of compressing a given source is defined as the smallest blocklength at which it is possible to compress that source at a specifically constrained rate and to within a specified excess-rate probability. This formulation parallels corresponding developments in statistics and computer science. For arbitrary sources, the sample complexity of general variable-length compressors is shown to be tightly coupled with the sample complexity of prefix-free codes and fixed-length codes. For memoryless sources, it is shown that the sample complexity is characterized not by the source entropy, but by its Rényi entropy of order 1/2. Explicity, nonasymptotic bounds on the sample complexity are obtained, and generalizations to Markov sources are established. Finally, bounds on the sample complexity of universal data compression are developed. The connection of this problem with identity testing and with the associated separation rates is explored and discussed.

Ioannis Kontoyiannis is the Churchill Professor of Mathematics of Information in the Department of Pure Mathematics and Mathematical Statistics at the University of Cambridge. He received his PhD in Electrical Engineering from Stanford University in 1998. Before joining Cambridge, he held appointments at Purdue University, Brown University, and the Athens University of Economics and Business.