2004-2005 seminars

We will describe definitions and algorithmic results for the ``census problem''. Informally, in a census individual respondents give private information to a trusted (and trustworthy) party, who publishes a sanitized version of the data. There are...

A celebrated 1976 theorem of Aumann asserts that honest, rational Bayesian agents will never "agree to disagree": if their opinions about any topic are common knowledge, then those opinions must be equal. Economists have written numerous papers...

In the late nineties Erickson proved a remarkable lower bound on the decision tree complexity of one of the central problems of computational geometry: given $n$ numbers, do any $r$ of them add up to $0$? His lower bound of $\Omega(n^{\lceil r/2...

A family of sets is called intersecting if the intersection of every two sets in the family is non empty. Many of the fundamental theorems in extremal set theory deal with the maximal size of an intersecting family under certain restrictions. A...