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.
From 2007 to 2009, I worked as a postdoctoral researcher at the Max-Planck-Institut für Informatik. Starting from August 2009, I will be an assistant professor at the University of Hong Kong. Click here for my new homepage.

Thesis

Approximation Algorithms for Bounded Dimensional Metric Spaces Carnegie Mellon University Technical Report CMU-CS-07-157. 2007.

Journal Papers

Metric Embeddings with Relaxed Guarantees T-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg, and Aleksandrs Slivkins. SIAM Journal on Computing. 2009.
Small Hop-diameter Sparse Spanners for Doubling Metrics T-H. Hubert Chan and Anupam Gupta. Discrete and Computational Geometry. 2008.

Conference Papers

An SDP Primal-Dual Algorithm for Approximating the Lovasz-Theta Function T-H. Hubert Chan, Kevin L. Chang and Rajiv Raman. IEEE International Symposium on Information Theory 2009.
Ultra-Low-Dimensional Embeddings for Doubling Metrics T-H. Hubert Chan, Anupam Gupta and Kunal Talwar. SODA 2008.
Approximating TSP on Metrics with Bounded Global Growth T-H. Hubert Chan and Anupam Gupta. SODA 2008.
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.
A Random-Surfer Web-Graph Model Avrim Blum, T-H. Hubert Chan, and Mugizi Robert Rwebangira. ANALCO 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.)

Manuscripts

A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics T-H. Hubert Chan and Khaled Elbassioni. DIMACS Technical Report 2009-01.