I have removed most of this website as it is out of date. My new alumni email address (see above) is correct though from now (January 2013)
and into the indefinite future. My old cs.brown.edu email address will continue to work for a while but will stop eventually.
I'm fond of:
- Foundations. Many 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.
- Simplicity. 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.
(Out of date.)
- Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank
Aggregation and Betweenness Tournament - in submission (with Marek
- Approximation Schemes for the Betweenness Problem in Tournaments
and Related Ranking Problems - in
submission (with Marek Karpinski).
- Online correlation clustering - to appear in STACS 2010 (with
Ocan Sankur and Claire Mathieu).
- Correlation Clustering with Noisy Input - SODA 2010 version and
presentation (with Claire
- Linear-Time Approximation Schemes for the Gale-Berlekamp Game
and Related Minimization Problems - Revised STOC
2009 version and presentation (with
- Yet Another Algorithm for Dense Max-Cut: Go Greedy - SODA 2008 paper and presentation (with Claire Mathieu).
- How to Rank with Few Errors: A PTAS for Weighted Feedback Arc Set on
Tournaments - draft journal
version, STOC 2007
version (out of date) and presentation.
My papers and presentations are copyrighted 2005-2009 by myself and/or their respective publishers and are made available here for personal use only.