Hubert Chan

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

Email: loginID(my first name) at cs.hku.hk

I am an associate professor at the University of Hong Kong. My main research interests are algorithms, combinatorial optimization, discrete metric space, security & privacy. 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.

Prospective PhD Students and Postdoctoral Fellows

I welcome applications from highly motivated and talented individuals who are interested in pursuing a PhD or a postdoctoral position in my research group. My work spans algorithms, combinatorial optimization, discrete metric spaces, security, privacy, and distributed systems. If you have a strong background in theoretical computer science or related areas and are excited about tackling challenging research problems, please review the detailed guidelines before contacting me.

Important: All prospective PhD students and postdoctoral candidates must read the instructions and application requirements here carefully. The document contains essential information about prerequisites, the application process, and what to include in your initial inquiry.

Due to the volume of emails, I may not be able to respond to messages that do not follow the instructions provided in the linked document.

Teaching

CSIS0351 Advanced Algorithm Analysis / CSIS8601 Probabilistic Method & Randomized Algorithms
- Fall 2009: CSIS8601
- Fall 2010: CSIS0351/CSIS8601
- Fall 2011: CSIS0351/CSIS8601
- Fall 2013: COMP8601
- Fall 2017: COMP8603
- Spring 2023: COMP8603
Foundations of Computer Science/Discrete Mathematics (CSIS1118 Spring 2010, CSIS1118 Spring 2011, CSIS1118 Spring 2012, ENGG1007 Fall 2012, CSIS1118/COMP2121 Spring 2013, COMP2121 Fall 2016, COMP2121 Fall 2017, COMP2121 Fall 2018, COMP2121 Fall 2019, COMP2121 Fall 2020, Fall 2021, Fall 2022, Fall 2023, Fall 2024, Fall 2025).
CSIS0250/COMP3250 Design and Analysis of Algorithms (Spring 2014)
CSIS1119/COMP2119 Introduction to Data Structures and Algorithms (Fall 2014, Fall 2015, Spring 2016, Fall 2018, Fall 2019, Fall 2020, Fall 2021, Fall 2022, Fall 2023, Fall 2024, Fall 2025)

Research

Please refer to my DBLP page for the latest list of publications.

Thesis

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

Journal Papers

On (1, epsilon)-Restricted Max-Min Fair Allocation Problem T.-H. Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu. Algorithmica 2018.
Spectral Properties of Hypergraph Laplacian and Approximation Algorithms T.-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, Chenzi Zhang. Journal of the ACM. 2018.
Path ORAM: An Extremely Simple Oblivious RAM Protocol Emil Stefanov, Marten van Dijk, Elaine Shi, T.-H. Hubert Chan, Christopher W. Fletcher, Ling Ren, Xiangyao Yu, Srinivas Devadas. Journal of the ACM. 2018.
Ranking on Arbitrary Graphs: Rematch via Continuous Linear Programming T.-H. Hubert Chan, Fei Chen, Xiaowei Wu, Zhichao Zhao. SIAM Journal on Computing. 2018.
A PTAS for the Steiner Forest Problem in Doubling Metrics T.-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang. SIAM Journal on Computing. 2018.
Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics T.-H. Hubert Chan, Shaofeng H.-C. Jiang. TALG 2018.
Analyzing Node-Weighted Oblivious Matching Problem via Continuous LP with Jump Discontinuity T.-H. Hubert Chan, Fei Chen, Xiaowei Wu. TALG 2018.
Online Submodular Maximization with Free Disposal T.-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang, Zhihao Gavin Tang. TALG 2018.
Distributed Private Data Analysis: Lower Bounds and Practical Constructions Elaine Shi, T.-H. Hubert Chan, Eleanor G. Rieffel, Dawn Song. TALG 2017.
Finding k most influential edges on flow graphs Petrie Wong, Cliz Sun, Eric Lo, Man Lung Yiu, Xiaowei Wu, Zhichao Zhao, T.-H. Hubert Chan, Ben Kao. Information Systems 2017.
On Hierarchical Routing in Doubling Metrics T-H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. TALG 2016.
Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree T-H. Hubert Chan, Minfgei Li and Li Ning. Algorithmica 2015.
New Doubling Spanners: Better and Simpler T-H. Hubert Chan, Mingfei Li, Li Ning, and Shay Solomon. SIAM Journal on Computing. 2015.
Fast Convergence for Consensus in Dynamic Networks T-H. Hubert Chan and Li Ning. TALG 2014.
An SDP Primal-Dual Algorithm for Approximating the Lovasz-Theta Function T-H. Hubert Chan, Kevin L. Chang and Rajiv Raman. Algorithmica 2013.
Approximating TSP on Metrics with Bounded Global Growth T-H. Hubert Chan and Anupam Gupta. SIAM Journal on Computing. 2012.
Capturing continuous data and answering aggregate queries in probabilistic XML Serge Abiteboul, T-H. Hubert Chan, Evgeny Kharlamov, Werner Nutt, and Pierre Senellart. ACM Transactions on Database Systems (TODS) 2011.
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, Anupam Gupta 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

Distributed Approximate k-Core Decomposition and Min-Max Edge Orientation: Breaking the Diameter Barrier T.-H. Hubert Chan, Mauro Sozio, Bintao Sun. IPDPS 2019 (Best Paper Award).
Communication Complexity of Byzantine Agreement, Revisited Ittai Abraham, T.-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, Elaine Shi. PODC 2019.
Locality-Preserving Oblivious RAM Gilad Asharov, T.-H. Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, Elaine Shi. EUROCRYPT 2019.
Consensus Through Herding T.-H. Hubert Chan, Rafael Pass, Elaine Shi. EUROCRYPT 2019.
Revisiting Opinion Dynamics with Varying Susceptibility to Persuasion via Non-Convex Local Search T.-H. Hubert Chan, Zhibin Liang, Mauro Sozio. WWW 2019.
Foundations of Differentially Oblivious Algorithms T.-H. Hubert Chan, Kai-Min Chung, Bruce M. Maggs, Elaine Shi. SODA 2019.
More is Less: Perfectly Secure Oblivious Algorithms in the Multi-server Setting T.-H. Hubert Chan, Jonathan Katz, Kartik Nayak, Antigoni Polychroniadou, Elaine Shi. ASIACRYPT 2018.
Perfectly Secure Oblivious Parallel RAM T.-H. Hubert Chan, Kartik Nayak, Elaine Shi. TCC 2018.
A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics T.-H. Hubert Chan, Haotian Jiang, Shaofeng H.-C. Jiang. ESA 2018.
Fully Dynamic k-Center Clustering T.-H. Hubert Chan, Arnaud Guerqin, Mauro Sozio. WWW 2018 (Honorable Mention).
Cache-Oblivious and Data-Oblivious Sorting and Applications T.-H. Hubert Chan, Yue Guo, Wei-Kai Lin, Elaine Shi. SODA 2018.
On the Depth of Oblivious Parallel RAM T.-H. Hubert Chan, Kai-Min Chung, Elaine Shi. ASIACRYPT 2017.
Oblivious Hashing Revisited, and Applications to Asymptotically Efficient ORAM and OPRAM T.-H. Hubert Chan, Yue Guo, Wei-Kai Lin, Elaine Shi. ASIACRYPT 2017.
Circuit OPRAM: Unifying Statistically and Computationally Secure ORAMs and OPRAMs T.-H. Hubert Chan, Elaine Shi. TCC 2017.
Maintaining Densest Subsets Efficiently in Evolving Hypergraphs Shuguang Hu, Xiaowei Wu, T.-H. Hubert Chan. CIKM 2017.
Online Submodular Maximization Problem with Vector Packing Constraint T-H. Hubert Chan, Shaofeng H.-C. Jiang, Zhihao Gavin Tang, Xiaowei Wu. ESA 2017.
Re-revisiting Learning on Hypergraphs: Confidence Interval and Subgradient Method Chenzi Zhang, Shuguang Hu, Zhihao Gavin Tang, T.-H. Hubert Chan. ICML 2017.
Large Scale Density-friendly Graph Decomposition via Convex Programming Maximilien Danisch, T.-H. Hubert Chan, Mauro Sozio. WWW 2017.
Online Submodular Maximization with Free Disposal: Randomization Beats 0.25 for Partition Matroids T.-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang, Zhihao Gavin Tang. SODA 2017.
A PTAS for the Steiner Forest Problem in Doubling Metrics T-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang. FOCS 2016.
Online Algorithms for Covering and Packing Problems with Convex Objectives Yossi Azar, Niv Buchbinder, T-H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph (Seffi) Naor, Debmalya Panigrahi. FOCS 2016.
Beating Ratio 0.5 for Weighted Oblivious Matching Problems Melika Abolhassani, T-H. Hubert Chan, Fei Chen, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Hamid Mahini, and Xiaowei Wu. ESA 2016.
Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics T-H. Hubert Chan, Shaofeng H.-C. Jiang. SODA 2016.
Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound Xiao Wang, T.-H. Hubert Chan, Elaine Shi. ACM Conference on Computer and Communications Security (CCS) 2015.
Finding Subgraphs with Maximum Total Density and Limited Overlap Oana Denisa Balalau, Francesco Bonchi, T.-H. Hubert Chan, Francesco Gullo, Mauro Sozio. WSDM 2015.
Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order T-H. Hubert Chan, Fei Chen, Shaofeng H.-C. Jiang. SODA 2015.
Oblivious Data Structures Xiao Shaun Wang, Kartik Nayak, Chang Liu, T-H. Hubert Chan, Elaine Shi, Emil Stefanov, and Yan Huang. ACM Conference on Computer and Communications Security (CCS) 2014.
SCORAM: Oblivious RAM for Secure Computation Xiao Shaun Wang, Yan Huang, T-H. Hubert Chan, abhi shelat, and Elaine Shi. ACM Conference on Computer and Communications Security (CCS) 2014.
Ranking on Arbitrary Graphs: Rematch via Continuous LP with Monotone and Boundary Condition Constraints T-H. Hubert Chan, Fei Chen, Xiaowei Wu, Zhichao Zhao. SODA 2014.
New Doubling Spanners: Better and Simpler T.-H. Hubert Chan, Mingfei Li, Li Ning, Shay Solomon. ICALP 2013.
Optimal Lower Bound for Differentially Private Multi-Party Aggregation T-H. Hubert Chan, Elaine Shi, Dawn Song. ESA 2012.
Optimizing Social Welfare for Network Bargaining Games in the Face of Unstability, Greed and Spite T-H. Hubert Chan, Fei Chen and Li Ning. ESA 2012.
Sparse Fault-Tolerant Spanners for Doubling Metrics with Bounded Hop-Diameter or Degree T-H. Hubert Chan, Mingfei Li and Li Ning. ICALP 2012.
Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams (over a Sliding Window) T-H. Hubert Chan, Mingfei Li, Elaine Shi and Wenchang Xu. Privacy Enhancing Technologies Symposium (PETS) 2012.
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.)

Patents

Privacy-preserving aggregation of time-series data. EP 2485430 A2.
High throughput blockchain consensus systems and methods with low finalization time. US20200104293A1.
Blockchain consensus systems and methods involving a time parameter. US20200134578A1.

Editorship

Information Processing Letters Board of Editors
Theory and Applications of Models of Computation, 10th International Conference TAMC 2013, Hong Kong, China, May 20-22, 2013. T.-H. Hubert Chan, Lap Chi Lau, Luca Trevisan (Eds.)

Program Committee

COCOA 2016 TPC Co-chair.
FCST 2011 Theoretical Computer Science Track Co-chair.
PC Member: DBCrowd 2013, TAMC 2013, ISAAC 2013, IPDPS 2014, ISAAC 2015, SPAA 2017, COCOON 2017, COCOA 2017, ISAAC 2018, SODA 2021, ISAAC 2021, PODS 2022.

External Grants

2025/26. Generalized Density Decompositions: A Unified Framework for Advancing Differential Privacy, Market Dynamics, and Online Allocation. 17203725. (Hong Kong RGC)
2023/24. Modular Composable Differentially Oblivious Distributed Mechanisms against Heterogeneous Adversaries. 17201823. (Hong Kong RGC)
2022/23. Decentralized, Private and Communication-Efficient Clustered Federated Learning among Self-Motivated Nodes in Byzantine Networks. 17203122. (Hong Kong RGC)
2021/22. Distributed Protocols for Allocation and Selection Problems among Self-Serving Agents: Fairness, Security, Communication Efficiency. 17202121. (Hong Kong RGC)
2020/21. Efficient and Private Distributed Protocols against Byzantine Nodes in Noisy Communication Networks. 17201220. (Hong Kong RGC)
2018/19. Private and I/O-Efficient Concurrent Data Structures and Parallel Algorithms. 17200418. (Hong Kong RGC)
2017/18. Spectral Analysis and Optimization Problems in Directed Hypergraph Diffusion Processes. 17200817. (Hong Kong RGC)
2016/17. Group Traveling Salesman Problems and Network Connectivity Problems on Fully Dynamic Metric Spaces with Bounded Growth. 17217716. (Hong Kong RGC)
2015/16. Primal-Dual Mathematical Programming Methods for Online Matching Problems with Generalized Constraints. 17202715. (Hong Kong RGC)
2014/15. Oblivious Matching Algorithms on Unknown (Hyper) Graphs. 17200214. (Hong Kong RGC)
2012/13. Privacy-Preserving Mechanisms on Multi-User Data in Ubiquitous Computing Environments. HKU719312E. (Hong Kong RGC Early Career Scheme)

Current Students

Xianrun Chen (PhD)
Qipeng Kuang (PhD)
Qian Liu (PhD)
Shinuo Ma (PhD)
Yan Ho Sen (MPhil)
Quan Xue (PhD)
Mengshi Zhao (PhD)