Publications
Approximation Algorithms
Other
About me and my research
See my CV for history.
I made a three-page summary of my
SODA 08, SPAA 08 and STOC 07 papers.
I'm fond of:
- Old, difficult and foundational problems. The above three papers make progress on problems that date from around 1961 (FAS-T), 1988 (parallel SCC) and 1995 (dense max cut).
- 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.