Warren Schudy Advised by Claire Mathieu PhD Candidate ws at cs.brown.edu Brown U. Computer Science Additional contact info

About me

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.

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

Publications

Approximation Algorithms

• Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament - in submission (with Marek Karpinski).
• 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 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.

Contact

The best ways to contact me are email and stopping by my office.

Email:	ws at cs dot brown dot edu
Office:	CIT 355 (Directions to building)
US Mail:	Warren Schudy Department of Computer Science Brown University, Box 1910 Providence, RI 02912-1910
Street address / Packages:	Warren Schudy Department of Computer Science Brown University 115 Waterman Street, 4th Floor Providence, RI 02912
Phone (front desk):	(401) 863-7600
Fax (shared):	(401) 863-7657

My papers and presentations are copyrighted 2005-2009 by myself and/or their respective publishers and are made available here for personal use only.