Warren Schudy PhD Candidate Brown University Dep't of Computer Science Theory/Approximation Algorithms CIT 355 (Directions) Advised by Claire Mathieu ws at cs.brown.edu

Publications

Approximation Algorithms

• Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems - in submission (with Marek Karpinski).
• Online correlation clustering - in submission (with Ocan Sankur and Claire Mathieu).
• Correlation Clustering with Noisy Input - SODA 2010 version and out of date presentation (with Claire Mathieu).
• Linear-Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems - Revised STOC 2009 version and presentation (with Marek Karpinski).
• 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. (with Claire Mathieu).

Other

• Bounding and Comparing Methods for Correlation Clustering Beyond ILP - ILP-NLP 2009 version, source code readme, source code tgz (with Micha Elsner)
• More Efficient Internal-Regret Minimizing Algorithms - COLT 2008 paper and presentation (with Amy Greenwald and Zheng Li).
• Finding Strongly Connected Components in Parallel using O(log^2 n) Reachability Queries - SPAA 2008 paper and presentation.

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

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.