Title: Blood on the Database: How Algorithms for Testing Blood Samples
can be Used for Database Integrity

Abstract:
This talk discusses combinatorial group testing, which began from work
on detecting diseases in blood samples taken from GIs in WWII. Given a
parameter d, which provides an upper bound on the number of defective
(e.g., diseased) samples, the main objective of such problems is to
design algorithms that identify all the defective samples without
explicitly testing all n samples. This classic problem has a number of
interesting modern applications, and we describe several such applications as well as new
algorithms. In particular, we address the problem of providing a way to protect against
the "Ferris Bueller" attack, so as to identify which records of a database have been
changed after an unauthorized intrusion, while using no additional memory.