Shaofeng Jiang 姜少峰

Center on Frontiers of Computing Studies
School of Computer Science
Peking University

Email: shaofeng.jiang at pku.edu.cn
Office: Room 206-1, Courtyard No.5, Jingyuan, Peking University
Mailing address: Courtyard No.5, Jingyuan, No.5 Yiheyuan Road, 100871, Beijing, P.R. China

I am an assistant professor at Peking University. Before joining PKU, I worked as an assistant professor at Aalto University, and I was a postdoctoral researcher at the Weizmann Institute of Science, hosted by Robert Krauthgamer. I obtained my PhD under the supervision of Hubert Chan from the University of Hong Kong, and bachelor's degree from Shandong University.

My research field is theoretical computer science, and I am interested in algorithms in a broad sense. Currently, I am working on algorithms for massive data sets, approximation algorithms and online algorithms.

Research

Journal Papers

  • Streaming Algorithms for Geometric Steiner Forest. Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý. TALG 2024.
  • Coresets for Kernel Clustering. Shaofeng H.-C. Jiang, Robert Krauthgamer, Jianing Lou, Yubo Zhang. Mach. Learn. 2024.
  • DAG Scheduling in Mobile Edge Computing. Guopeng Li, Haisheng Tan, Liuyan Liu, Hao Zhou, Shaofeng H.-C. Jiang, Zhenhua Han, Xiang-Yang Li, Guoliang Chen. ToN 2023.
  • Online Approximation Scheme for Scheduling Heterogeneous Utility Jobs in Edge Computing. Chi Zhang, Haisheng Tan, Haoqiang Huang, Zhenhua Han, Shaofeng H.-C. Jiang, Guopeng Li, Xiang-Yang Li. ToN 2022.
  • SPIN: BSP Job Scheduling With Placement-Sensitive Execution. Zhenhua Han, Haisheng Tan, Shaofeng H.-C. Jiang, Wanli Cao, Xiaoming Fu, Lan Zhang, Francis C. M. Lau. ToN 2021.
  • Asymptotically Optimal Online Caching on Multiple Caches With Relaying and Bypassing. Haisheng Tan, Shaofeng H.-C. Jiang, Zhenhua Han, Mingxia Li. ToN 2021.
  • A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics. T-H. Hubert Chan, Haotian Jiang, Shaofeng H.-C. Jiang. TALG 2020.
  • OnDisc: Online Latency-Sensitive Job Dispatching and Scheduling in Heterogeneous Edge-Clouds. Zhenhua Han, Haisheng Tan, Xiang-Yang Li, Shaofeng H.-C. Jiang, Yupeng Li, Francis C.M. Lau. ToN 2019.
  • Joint Online Coflow Routing and Scheduling in Data Center Networks. Haisheng Tan, Shaofeng H.-C. Jiang, Yupeng Li, Xiang-Yang Li, Chenzi Zhang, Zhenhua Han, Francis C.M. Lau. ToN 2019.
  • A PTAS for the Steiner Forest Problem in Doubling Metrics. T-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang. SICOMP 2018.
  • Online Submodular Maximization with Free Disposal. T.-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang, Zhihao Gavin Tang. TALG 2018.
  • Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics. T-H. Hubert Chan, Shaofeng H.-C. Jiang. TALG 2018.

    Conference Papers

  • Dynamic Facility Location in High Dimensional Euclidean Spaces. Sayan Bhattacharya, Gramoz Goranci, Shaofeng H.-C. Jiang, Yi Qian, Yubo Zhang. ICML 2024 (spotlight, 3.5% acceptance rate).
  • Algorithms for the Generalized Poset Sorting Problem. Shaofeng H.-C. Jiang, Wenqian Wang, Yubo Zhang, Yuhao Zhang. ICALP 2024.
  • Fully Scalable MPC Algorithms for Clustering in High Dimension. Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý. ICALP 2024.
  • Moderate Dimension Reduction for k-Center Clustering. Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir. SoCG 2024.
  • Fully Dynamic Algorithms for Euclidean Steiner Tree. T-H. Hubert Chan, Gramoz Goranci, Shaofeng H.-C. Jiang, Bo Wang, Quan Xue. WALCOM 2024.
  • Near-Optimal Quantum Coreset Construction Algorithms for Clustering. Yecheng Xue, Xiaoyu Chen, Tongyang Li, Shaofeng H.-C. Jiang. ICML 2023.
  • The Power of Uniform Sampling for k-Median. Lingxiao Huang, Shaofeng H.-C. Jiang, Jianing Lou. ICML 2023.
  • Streaming Euclidean Max-Cut: Dimension vs Data Reduction. Xiaoyu Chen, Shaofeng H.-C. Jiang, Robert Krauthgamer. STOC 2023.
  • Near-optimal Coresets for Robust Clustering. Lingxiao Huang, Shaofeng H.-C. Jiang, Jianing Lou, Xuan Wu. ICLR 2023 (top 5%).
  • On The Relative Error of Random Fourier Features for Preserving Kernel Distance. Kuan Cheng, Shaofeng H.-C. Jiang, Luojian Wei, Zhide Wei. ICLR 2023.
  • The Power of Uniform Sampling for Coresets. Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, Xuan Wu. FOCS 2022.
  • Streaming Facility Location in High Dimension via Geometric Hashing. Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, Mingwei Yang. FOCS 2022.
  • Streaming Algorithms for Geometric Steiner Forest. Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý. ICALP 2022.
  • Online Facility Location with Predictions. Shaofeng H.-C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, Yubo Zhang. ICLR 2022.
  • Online File Caching in Latency-Sensitive Systems with Delayed Hits and Bypassing. Chi Zhang, Haisheng Tan, Guopeng Li, Zhenhua Han, Shaofeng H.-C. Jiang, Xiang-Yang Li. INFOCOM 2022.
  • Coresets for Clustering with Missing Values. Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu. NeurIPS 2021 (spotlight).
  • Coresets for Clustering in Excluded-minor Graphs and Beyond. Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu. SODA 2021.
  • Coresets for Clustering in Graphs of Bounded Treewidth. Daniel Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu. ICML 2020.
  • Scheduling Placement-Sensitive BSP Jobs with Inaccurate Execution Time Estimation. Zhenhua Han, Haisheng Tan, Shaofeng H.-C. Jiang, Xiaoming Fu, Wanli Cao, Francis C.M. Lau. INFOCOM 2020.
  • Online Dispatching and Scheduling of Jobs with Heterogeneous Utilities in Edge Computing. Chi Zhang, Haisheng Tan, Haoqiang Huang, Zhenhua Han, Shaofeng H.-C. Jiang, Nikolaos Freris, XiangYang Li. Mobihoc 2020.
  • Coresets for Clustering with Fairness Constraints. Lingxiao Huang, Shaofeng H.-C. Jiang, Nisheeth Vishnoi. NeurIPS 2019.
  • Coresets for Ordered Weighted Clustering. Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu. ICML 2019.
  • Camul: Online Caching on Multiple Caches with Relaying and Bypassing. Haisheng Tan, Shaofeng H.-C. Jiang, Zhenhua Han, Liuyan Liu, Kai Han, Qinglin Zhao. INFOCOM 2019.
  • epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics. Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, Xuan Wu. FOCS 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.
  • Online Submodular Maximization Problem with Vector Packing Constraint. T-H. Hubert Chan, Shaofeng H.-C. Jiang, Zhihao Gavin Tang, Xiaowei Wu. ESA 2017.
  • Online Submodular Maximization with Free Disposal: Randomization Beats 1/4 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.
  • Efficient Online Coflow Routing and Scheduling. Yupeng Li, Shaofeng H.-C. Jiang, Haisheng Tan, Chenzi Zhang, Guihai Chen, Jipeng Zhou, Francis C.M. Lau. Mobihoc 2016.
  • Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics. T-H. Hubert Chan, Shaofeng H.-C. Jiang. SODA 2016.
  • 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.

    Teaching

  • A Programming course for undergraduate students at Peking University.
  • Selected Topics in Social Networks and Markets for graduate students at Peking University.
  • The 2021 Spring offering of the Programming 2 (CS-A1120) course at Aalto University (use guest role to access).
  • The coach of HKU ACM-ICPC Team during September 2014 - August 2017.

    • Program Committee

    IPDPS 2019, SWAT 2022, NeurIPS 2024 (area chair)

    Current Students

  • Jianing Lou (PhD)
  • Guichen Gao (PhD)
  • Yubo Zhang (PhD)

    • Last updated: June 13, 2024.