Many organizations publish sensitive data for the purpose of finding trends in areas such as public health or product consumption. In the interest of privacy, attributes that clearly identify individuals, such as name and Social Security number, are removed. Nevertheless, it has been shown that such de-identified tables can often be used to uniquely identify individuals using a combination of attributes such as gender, zipcode, and date of birth.
Proposed methods for preventing this type of privacy breech give rise to many interesting theoretical problems. This talk will survey some of these privacy-preserving techniques, with an emphasis on the algorithms and analysis that they require. This will include some known results as well as several open problems.