Lichen Zhang's Homepage

Short Bio

I'm a 5th-year Ph.D. candidate at MIT Mathematics and I'm very fortunate to be advised by Professor Jonathan Kelner. I earned my bachelor’s and master’s degrees in computer science from Carnegie Mellon University, advised by Professor Gary Miller. I currently work on alignment science as an Anthropic Safety Fellow. I previously worked on developing efficient algorithms for machine learning, with a focus on optimization, sketching, differential privacy and quantum computing. I'm supported by a Simons Dissertation Fellowship in Mathematics.

Publications (Author names in alphabetical order)

• Sublinear Time Quantum Sensitivity Sampling (arxiv link).
  Zhao Song, David P. Woodruff and Lichen Zhang.
  NeurIPS, 2026.
• Graph-based Nearest Neighbors with Dynamic Updates via Random Walks (arxiv link).
  Nina Mishra, Yonatan Naamad, Tal Wagner and Lichen Zhang.
  ICLR, 2026.
• Sublinear Time Quantum Algorithm for Attention Approximation (arxiv link).
  Zhao Song, Jianfei Xue, Jiahao Zhang and Lichen Zhang.
  ICLR, 2026.
• Differential Privacy for Euclidean Jordan Algebra with Applications to Private Symmetric Cone Programming (arxiv link).
  Zhao Song, Jianfei Xue and Lichen Zhang.
  NeurIPS, 2025.
• On Differential Privacy for Adaptively Solving Search Problems via Sketching (arxiv link).
  Shiyuan Feng, Ying Feng, George Z. Li, Zhao Song, David P. Woodruff and Lichen Zhang.
  ICML, 2025. Selected for Oral Presentation (top 1% of submissions).
• Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation (arxiv link).
  Zhao Song, Mingquan Ye, Junze Yin and Lichen Zhang.
  ICLR, 2025.
• Faster Algorithms for Structured Linear and Kernel Support Vector Machines (arxiv link).
  Yuzhou Gu, Zhao Song and Lichen Zhang.
  ICLR, 2025.
• Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk (arxiv link).
  Yuzhou Gu, Nikki Lijing Kuang, Yi-An Ma, Zhao Song and Lichen Zhang.
  NeurIPS, 2024.
• Solving Attention Kernel Regression Problem via Pre-conditioner (arxiv link).
  Zhao Song, Junze Yin and Lichen Zhang.
  AISTATS, 2024.
• Fast Dynamic Sampling for Determinantal Point Processes (link).
  Zhao Song, Junze Yin, Lichen Zhang and Ruizhe Zhang.
  AISTATS, 2024.
• Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time (arxiv link).
  Yuzhou Gu, Zhao Song, Junze Yin and Lichen Zhang.
  ICLR, 2024.
• Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time (arxiv link, long talk).
  Zhao Song, Lichen Zhang and Ruizhe Zhang.
  ITCS, 2024.
• Convex Minimization with Integer Minima in ~O(n^4) Time (arxiv link, long talk).
  Haotian Jiang, Yin Tat Lee, Zhao Song and Lichen Zhang.
  SODA, 2024.
• Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance (arxiv link, short talk).
  Zhao Song, Xin Yang, Yuanyuan Yang and Lichen Zhang.
  ICML, 2023.
• Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability (arxiv link, short talk).
  Zhao Song, Yitan Wang, Zheng Yu and Lichen Zhang.
  ICML, 2023.
• A Nearly-Optimal Bound for Fast Regression with \ell_\infty Guarantee (arxiv link).
  Zhao Song, Mingquan Ye, Junze Yin and Lichen Zhang.
  ICML, 2023.
• Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching (arxiv link).
  S. Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang and Tianyi Zhou.
  ICALP, 2023.
• An Online and Unified Algorithm for Projection Matrix Vector Multiplication with Application to Empirical Risk Minimization (link).
  Lianke Qin, Zhao Song, Lichen Zhang and Danyang Zhuo.
  AISTATS, 2023.
• Dynamic Tensor Product Regression (arxiv link).
  Aravind Reddy, Zhao Song and Lichen Zhang.
  NeurIPS, 2022.
• Fast Sketching of Polynomial Kernels of Polynomial Degree (arxiv link).
  Zhao Song, David P. Woodruff, Zheng Yu and Lichen Zhang.
  ICML, 2021.

Manuscripts

• Faster Algorithm for One-Sided Kadison-Singer via Furthest-Neighbor Search (pdf).
  Zhao Song, Zhaozhuo Xu and Lichen Zhang.

AI-Assisted Manuscripts

These manuscripts were written with heavy assistance from large language models. The authors are responsible for the results and their correctness.

• Matrix Spencer: Eight Standard Deviations Suffice and An Almost-Linear Time Algorithm for Dense Input (arxiv link).
  Zhao Song and Lichen Zhang.
• A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra (arxiv link).
  Zhao Song and Lichen Zhang.
• Hadamard Flattening and Gaussian Pooling Sketch for Least Squares with Coordinate-wise Guarantee (arxiv link).
  Zhao Song and Lichen Zhang.

Master Thesis

• Speeding Up Optimizations via Data Structures: Faster Search, Sample and Maintenance (link).