Group testing and algorithmic applications

20^th May 2013, 16:00 ALT
Prof. Ely Porat
Department of Computer Science
Bar-Ilan University
Israel

and
Department of Mathematics
University of Michigan
USA

Abstract

Group testing is a prominent problem in combinatorics: A small set of
ill individuals should be identified out of a large group using only
queries (tests) of the form “Does the set X contain an ill
individual?”.
I will present an overview of the field along several surprising
algorithmic applications, including pattern matching, sketching and
homomorphic signatures.