Title: Approximate Privacy: Foundations and Quantification

Increasing use of computers and networks in business, government, recreation, and almost all aspects of daily life has led to a proliferation of online sensitive data about individuals and organizations. Consequently, concern about the privacy of these data has become a top priority, particularly those data that are created and used in electronic commerce. There have been many formulations of privacy and, unfortunately, many negative results about the feasibility of maintaining privacy of sensitive data in realistic networked environments. We formulate communication-complexity-based definitions, both worst-case and average-case, of a problem's privacy-approximation ratio. We use our definitions to investigate the extent to which approximate privacy is achievable in various standard problems, including the 2nd-price Vickrey auction and the set-intersection problem.

Joint work with Aaron Jaggard and Michael Schapira.

Title: Implicit Hitting Set Problems and Multi-Genome Alignment

A hitting set problem is specified by a finite ground set, a weight for each element, and a collection S of subsets of the ground set. A hitting set is a set having a nonempty intersection with each subset in S. We seek a hitting set of minimum total weight.

An implicit hitting set problem is one in which the collection S is not specified explicitly, but is accessible via a polynomial-time membership oracle. Many NP-hard problems can be described as implicit hitting set problems.

We will present a general algorithmic scheme for solving implicit hitting set problems, and then customize the scheme for the problem of optimal alignment of several genomes. The resulting algorithm has been applied to a suite of 4096 problems arising in the alignment of worm genomes. Our method produced provably optimal solutions to 4060 of these problems and provably near-optimal solutions to the remaining 36. This is joint work with Erick Moreno Centeno.

Title: Some Challenges in the Theory of Infectious Diseases

The theory of infectious diseases is one of the oldest areas of research in mathematical biology. This lecture will briefly review the classical literature, and raise new challenges focusing on evolutionary changes in viruses and bacteria, the interaction of diseases, and economic epidemiology.

Title: Port security, anthrax, and drug safety: A DIMACS medley

The DIMACS Adverse Event/Disease Reporting, Surveillance and Analysis working group was active about five years ago. In this talk I will describe a diverse set of currently active research projects that trace their roots to working group activities and relationships.

Title: Polynomial Time Solvability and Invariants of the Witness Set

This is an exploratory talk based on the vision that for large classes of important NP problems the membership in P of a given problem depends on the existence of certain invariants on the witness set. First we focus on the class of constraint satisfaction problems (CSPs), where the existence of so-called polymorphism of certain types are known to be in relation with polynomial time solvability. This was established by Jeavons and co-authors, and by now their theory has an extensive literature. G. Kun and M. S. have recently given a very combinatorial characterization of these crucial invariants. We suggest that a similar connection may exist for well known NP problems such as linear programming and graph isomorphism that are not CSPs.

The final goal would be to build a theory that explains (and predicts) the success of solving some problems while establishes the hardness of others, based on these invariants.

Title: Games in Networks: the price of anarchy and learning

Network games play a fundamental role in understanding behavior in many domains, ranging from communication networks through markets to social networks. Such networks are used, and also evolve due to selfish behavior of the users and owners. In light of these competing forces, it is surprising how efficient these networks are. It is an exciting challenge to understand the operation and success of these networks in game theoretic terms: what principles of interaction lead selfish participants to form such efficient networks?

We will focus on congestion games, and study the degradation of quality of solution caused by the selfish behavior of users. We model users as learning algorithms, and show that natural learning behavior can avoid bad outcomes predicted by the price of anarchy in atomic congestion games such as the load-balancing game. We use tools from the theory of dynamical systems and algebraic geometry to show when players use a class of natural learning algorithms the distribution of play converges to the set of weakly stable equilibria, and that the set of weakly stable equilibria are the pure Nash equilibria with probability 1 when congestion costs are selected at random independently on each edge (from any monotonically parameterized distribution).

Title: The Challenge of the DIMACS Computational Challenges

There have been nine computational challenges associated with the various special years of DIMACS. The computational challenges have proven to be an important impetus to work in computational optimization. I'll review the various computational challenges (with an emphasis on the second challenge, which I know best) and outline some of the successes. But these Challenges are not easy, so I will also describe some of the difficulties in the Challenges and some future directions.

Title: The Combinatorial Side of Statistical Physics

Thanks in part to DIMACS, the past fifteen years have seen a huge boom in work at the interface of statistical physics, combinatorics, probability, and the theory of computing. We'll try to give an indication of what these fields have in common that has gotten so many people excited, and will present a few examples of the new insights that have emerged from the collaboration.