RYAN O’DONNELL
Assistant Professor, Computer Science
www

My main research interests are in computational complexity, especially hardness of approximation and computational learning theory. I also have strong interests in dicrete harmonic analysis and in probability.

There is a pat view of computational complexity which holds that almost every natural algorithmic task is either solvable efficiently (in polynomial time) or is NP-hard. Factoring and Graph-Isomorphism are frequently cited as the "only" natural problems to resist such a classification. However, this view is not at all accurate. In fact, there are two major genres of important, intensively-studied algorithmic tasks containing many problems not known to be in P and not known to be NP-hard:

• Approximation problems -- finding solutions to classic NP-hard problems (e.g., Max-Cut, Max-SAT, Vertex-Cover) that are within a small factor of being optimal.
• Learning problems -- identifying certain kinds of boolean functions given only random examples, (x, f(x)).

I am working on problems in both areas.