Hubert Chan

Department of Computer Science
Chow Yei Ching Building
The University of Hong Kong
Pokfulam Road
Hong Kong

Email: loginID at cs.hku.hk

I am an assistant professor at the University of Hong Kong. My main research interests are approximation algorithms, combinatorial optimization and metric spaces. I have defended my PhD thesis in September 2007 under the supervision of my advisor Anupam Gupta at Carnegie Mellon University. From 2007 to 2009, I worked as a postdoctoral researcher at the Max-Planck-Institut für Informatik.

Teaching

CSIS0351 Advanced Algorithm Analysis / CSIS8601 Probabilistic Method & Randomized Algorithms
- Fall 2009: CSIS8601
- Fall 2010: CSIS0351/CSIS8601
- Fall 2011: CSIS0351/CSIS8601
CSIS1118 Foundations of Computer Science (Spring 2010, Spring 2011, Spring 2012).

Research

Thesis

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

Journal Papers

Private and Continual Release of Statistics T.-H. Hubert Chan, Elaine Shi and Dawn Song. ACM Transactions on Information and System Security (TISSEC) 2011.
A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics T.-H. Hubert Chan and Khaled Elbassioni. Discrete and Computational Geometry. 2011
Ultra-low-dimensional Embeddings for Doubling Metrics T.-H. Hubert Chan and Kunal Talwar. Journal of the ACM. 2010.
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

Privacy-Preserving Stream Aggregation with Fault Tolerance T-H. Hubert Chan, Elaine Shi, Dawn Song. Financial Cryptography and Data Security (FC) 2012.
Oblivious RAM with O(log N ^ 3) Worst-Case Cost Elaine Shi, T-H. Hubert Chan, Emil Stefanov, Mingfei Li. Asiacrypt 2011.
Fast Convergence for Consensus in Dynamic Networks T-H. Hubert Chan and Li Ning. ICALP 2011.
Privacy-Preserving Aggregation of Time-Series Data Elaine Shi, T-H. Hubert Chan, Eleanor Rieffel, Richard Chow and Dawn Song. Network & Distributed System Security Symposium (NDSS) 2011.
Private and Continual Release of Statistics T-H. Hubert Chan, Elaine Shi and Dawn Song. ICALP 2010.
Aggregate Queries for Discrete and Continuous Probabilistic XML Serge Abiteboul, T-H. Hubert Chan, Evgeny Kharlamov, Werner Nutt, and Pierre Senellart. International Conference on Database Theory (ICDT) 2010.
A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics T-H. Hubert Chan and Khaled Elbassioni. SODA 2010.
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.)