My research is patiently supervised by Dr. Oliver Johnson and kindly funded by the University of Bristol through the University of Bristol Postgraduate Research Scholarship.

I am currently working on two different topics: the notion of typicality in discrete ergodic processes and algorithms for group testing.

In information-theoretical contexts, a string produced by a discrete random process is usually called typical if its probability is bounded by two suitable exponentials controlled by the entropy of the process. In 1989 Grassberger conjectured that the entropy of a random process could be estimated using the average of the lengths of those prefixes of substrings that have a single occurrence within the original string (match-lengths). The conjecture turned out to be true (Shields, 1992 and 1997), and while running some simulations I had the chance to observe a rather striking correlation between substrings that had "too short" (/too long) a match-length and substrings that had too low (/too high) a probability. Do the sets of non-typical substrings asymptotically coincide with the sets of too-short and too-long strings? What is the rate of convergece? If there is convergence, how can we use it to study dependencies among substrings?

Group testing is the problem of finding efficient algorithms to detect a sparse subset of a set. In particular, consider a family of N identical items of which K are different from the remaining N-K, assuming K is much smaller than N. We aim to find the K "defective" elements with as few test as possible. The idea behing group testing algorithms is that having a procedure which, in a single shot, is able to say whether a defective element is contained in a subset of items may speed up detection. It turns out that this is indeed the case.

A key characteristic of group testing problems is their recently aknowledged affinity with information theory (Atia and Saligrama, 2010), and more specifically with channel coding. My work on group testing aims at further exploring the connections between this detection problem and information theory, in order to produce efficient algorithms as well as more general statements concerning the tractability of classes of group testing problems.

In this framework, together with Oliver Johnson and Matthew Aldridge, we have been able to introduce a concept of capacity for group testing problems. This quantity follows the analogy introduced by Atia and Saligrama and works as an efficiency threshold for families of group testing problems, which we classify according to their error model.

The Capacity of Adaptive Group Testing, with Matthew Aldridge and Oliver Johnson, submitted to the 2013 International Symposium on Information Theory (ISIT);
Group Testing Algorithms: Bounds and Simulations, with Matthew Aldridge and Oliver Johnson, in preparation.