Exponential Algorithms

I am offering a graduate seminar this quarter, Tuesdays and Thursdays at 12:30, on the subject of exponential algorithms. This is a hot topic in algorithms research combining ideas from AI (constraint programming and large-scale search for solutions of NP-hard problems) with theoretical computer science (worst case analysis and algorithmic improvement). There is also plenty of room for new research due to the large gap between experimentally measured performance and known worst case bounds.

There is no assigned text, due to the novelty of the subject area; instead I'll build up a set of papers to read over the course of the quarter. The format will be lecture and discussion, with a small amount of homework to help encourage everyone to keep up. All ICS grad students are welcome but I recommend a strong understanding of analysis of algorithms, at least at the ICS 161 level.