Publications
Approximation Algorithms
Other
About me and my research
My thesis proposal will be on Monday October 5 starting at 9:15 am.
See my CV for history.
I'm fond of:
- Old, difficult and foundational problems. Most of the problems I have studied so far date from the
1960s and 1990s.
- Applicability. I prefer problems that seem likely to have direct or indirect impact on forseeable applications. I love things like Turing machines which have an obvious (though indirect) connection to applications, but I'm not the type to invent number theory 100 years before its applications appear.
- Simple algorithms. I generally would rather have an extra log n factor in the runtime than an extra 3 pages in the description of the algorithm.
- Randomization. I've observed a totally unplanned pattern that my papers usually involve probability.
Slightly more concretely, I am interested in parts of:
- Approximation Algorithms
- Game theory and Voting
- Machine learning
- Branch and bound and related techniques for
practical combinatorial optimization.
- Programming languages and compilation
- Logic and verification
Personal webpage
My papers and presentations are copyrighted 2005-2008 by myself and/or by their respective publishers and are made available here for personal use only.