Hubert Chan Computer Science Department Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 15213 USA I have defended my PhD thesis in September 2007 under the supervision of my advisor Anupam Gupta. I am now working as a postdoctoral researcher at the Max-Planck-Institut für Informatik. Click here for my new homepage.

Thesis

• Approximation Algorithms for Bounded Dimensional Metric Spaces

Publications

• Ultra-Low-Dimensional Embeddings for Doubling Metrics T-H. Hubert Chan, Anupam Gupta and Kunal Talwar. SODA 2008 (To appear).
• Approximating TSP on Metrics with Bounded Global Growth T-H. Hubert Chan and Anupam Gupta. SODA 2008 (To appear).
• A Theory of Loss-Leaders: Making Money by Pricing Below Cost Maria-Florina Balcan, Avrim Blum, T-H. Hubert Chan and MohammadTaghi Hajiaghayi. WINE 2007.
• Multi-dimensional Range Query over Encrypted Data Elaine Shi, John Bethencourt, T-H. Hubert Chan, Dawn Song and Adrian Perrig. IEEE Symposium on Security and Privacy 2007.
• Spanners with Slack T-H. Hubert Chan, Michael Dinitz and Anupam Gupta. ESA 2006.
• A Tight Lower Bound for the Steiner Point Removal Problem on Trees T-H. Hubert Chan, Donglin Xia, Goran Konjevod and Andrea Richa. APPROX 2006.
• Small Hop-diameter Sparse Spanners for Doubling Metrics T-H. Hubert Chan and Anupam Gupta. SODA 2006.
• Metric Embeddings with Relaxed Guarantees Ittai Abraham, Yair Bartal, T-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg, Ofer Neiman, and Aleksandrs Slivkins. FOCS 2005.
• On Hierarchical Routing in Doubling Metrics T-H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. SODA 2005. (Complete proof for the bounded degree spanner construction.)

Workshop

• A Random-Surfer Web-Graph Model Avrim Blum, T-H. Hubert Chan, and Mugizi Robert Rwebangira. ANALCO 2006.

Presentation Slides

• Aladdin Workshop May, 2005
• Theory Lunch March 3, 2004