Majorities, Secrecies and Sparsities: the many facets of group testing.

Selection by intersection is a powerful paradigm which has been proven useful in several and diverse scenarios. Consider the following three problems:

1. given is a stream of data on which we are interested to compute statistics (on the fly, considering that the stream is too large to be stored in memory). Think of a huge sequence of numbers and we are to report  the most frequent items without storing the sequence. Counting majorities are special cases of such setting.

2. how can one define fingerprints to mark digital products delivered to authorized users in order to be able to detect illegal copies and possibly  trace them back to the user who produced them?

3. how can we  identify subtle genetic variations linked to medical disorders using high throughput DNA sequencing technologies.

Starting from these examples, we will describe some basic techniques, recent results and open questions in the area of group testing.