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 a 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 the University of 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.

Prediction-Aided Sequential Communication of Individual Sequences with Distortion Guarantees

Giuseppe Durisi, Chalmers University of Technology

Abstract: We consider a prediction-powered communication setting, in which transceivers, equipped with pre-trained predictors, communicate under zero-delay constraints with strict distortion guarantees that hold for every sequence. Specifically, we propose zero-delay compression algorithms leveraging online conformal prediction to provide per-sequence guarantees on the distortion of reconstructed sequences over error-free and packet-erasure channels with feedback. For erasure channels, we introduce a doubly-adaptive conformal update to compensate for channel-induced errors and derive sufficient conditions on erasure statistics to ensure distortion constraints. Joint work with Matteo Zecchin, Unnikrishnan Kunnath Ganesan, Petar Popovski, and Osvaldo Simeone.

Giuseppe Durisi is a Professor in the Communication Systems Group at Chalmers University of Technology, Gothenburg. He received the Laurea degree (summa cum laude) in 2001 and the PhD degree in 2006, both from Politecnico di Torino, Italy, and from 2002 to 2006 was with Istituto Superiore Mario Boella, Torino. He was a Postdoctoral Researcher at ETH Zurich from 2006 to 2010 before joining Chalmers.