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

Publications

Approximation Algorithms

• Linear-Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems - working paper (with Marek Karpinski).
• Correlation Clustering with Noisy Input - working paper (with Claire Mathieu).
• Yet Another Algorithm for Dense Max-Cut: Go Greedy - SODA '08 paper and presentation (with Claire Mathieu).
• How to Rank with Few Errors: A PTAS for Weighted Feedback Arc Set on Tournaments - STOC 2007 version, and older and longer ECCC TR06-144 version (with Claire Mathieu). Slides: 20-minute presentation or one-hour presentation.

Other

• More Efficient Internal-Regret Minimizing Algorithms - COLT '08 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

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

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.