Chris Harrelson
581 Soda Hall, UC Berkeley
Work: 510-643-5425
Home: 510-666-0483
Since 2004, I've been working at Google. My project is Google Transit,
which aims to make public transit information as widely available as possible. (information easy to reach = people make
more informed choices!)
Mailing lists
Publications
- Approximate classification via earthmover metrics (with Aaron Archer,
Jittat Fakcharoenphol, Robert Krauthgamer, Kunal Talwar and Eva Tardos)
Conference version (SODA 2004): ps.gz
- (2003) Limited randomness LT codes (with Lawrence Ip and Wei Wang)
Conference version (Allerton 2003): ps.gz
- A polynomial-time tree decomposition to minimize congestion (with Kris Hildrum and Satish Rao)
Conference version (SPAA 2003): ps.gz
- The k-traveling repairman problem (with Jittat Fakcharoenphol and Satish Rao)
Conference version (SODA 2003): ps.gz
- An improved approximation algorithm for the 0-extension problem (with Jittat Fakcharoenphol, Satish Rao and Kunal Talwar)
Conference version (SODA 2003): ps.gz
Technical reports
- Computing the shortest path: A* search meets graph theory
(with Andrew Goldberg)
MSR technical report (March 2004): ps.gz
- (2001) Quantum clock synchronization with one qubit (with Iordanis Kerenidis)
LANL
preprint server,
(article cs.CC/0103021): ps.gz
Past research
-
An analysis of distributed, Unix-based routers (project report for CS252, spring 2001):
ps.gz
- project page
- (presentation slides: zipped powerpoint)
-
Smoothed analysis and the Simplex algorithm (project talk for CS278, spring 2001):
ps.gz
-
Some theory and applications of linear logic (project report for CS263,
fall 2000):
ps.gz
- (presentation slides: ps.gz)
- The Vampyre theorem prover, spring 2000: homepage
-
Sampling from two-way contingency tables (project report for CS294-8, fall
1999): ps.gz
- (presentation slides: ps.gz)
- PAM, a Program Anaysis Mode for Emacs, 1998-1999: homepage
Past teaching