skip to content

Department of Applied Mathematics and Theoretical Physics

The classical coupon collector’s problem asks how many random draws with replacement are needed to collect all n distinct items. In this talk, I will discuss an extension in which information is encoded before storage and must be recovered from random samples. In this setting, we encode k information symbols into n coded symbols and sample the coded symbols uniformly at random with replacement. The goal is to choose the code so that a requested subset of the information symbols can be decoded from as few samples as possible on average. The problem is motivated by DNA-based data storage, where reducing the number of sequencing reads can lower both retrieval time and cost.


Maximum distance separable (MDS) codes are optimal for full recovery. Surprisingly, for random access to individual information symbols, MDS codes and several other familiar code families have a worst-case expected retrieval time of at least k samples, which is equal to the uncoded benchmark. I will explain how a property called recovery balance accounts for this behaviour and show how to construct codes that break this balance and bring the expected retrieval time below k for every information symbol. I will conclude with recent results on random access to files, where each request is for a block of information symbols.

Further information

Time:

18Nov
Nov 18th 2026
14:00 to 15:00

Venue:

MR5, CMS Pavilion A

Series:

Information Theory Seminar