Publications
(Following conventions of math and theoretical computer science, authors are listed in alphabetical order.)
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness.
with Elena Gribelyuk, David P. Woodruff, Huacheng Yu, and Samson Zhou
STOC 2025
Space Complexity of Minimum Cut Problems in Single-Pass Streams.
with Matthew Ding, Alexandro Garces, Jason Li, Jelani Nelson, Vihan Shah, and David P. Woodruff
ITCS 2025
A Theory for Compressibility of Graph Transformers for Transductive Learning.
Hamed Shirzad, Honghao Lin, Balaji Venkatachalam, Ameya Velingker, David P. Woodruff,
and Danica J. Sutherland (contributional order)
Machine Learning and Compression Workshop at NeurIPS 2024.
Even Sparser Graph Transformers.
Hamed Shirzad, Honghao Lin, Balaji Venkatachalam, Ameya Velingker, David P. Woodruff,
and Danica J. Sutherland (contributional order)
NeurIPS 2024
A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches.
with Elena Gribelyuk, David P. Woodruff, Huacheng Yu, and Samson Zhou
FOCS 2024
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms.
with Yi Li and David P. Woodruff
ICLR 2024
Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut.
with Yu Cheng, Max Li, Zi-Yi Tai, David P. Woodruff, and Jason Zhang
PODS 2024
$\ell_p$-Regression in the Arbitrary Partition Model of Communication.
with Yi Li and David P. Woodruff
COLT 2023
Learning the Positions in CountSketch.
with Yi Li, Simin Liu, Ali Vakilian, and David P. Woodruff
ICLR 2023 (spotlight)
The $\ell_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines.
with Yi Li and David P. Woodruff
SODA 2023
Streaming Algorithms with Large Approximation Factors.
with Yi Li, David P. Woodruff, and Yuheng Zhang
RANDOM 2022
Learning-Augmented Binary Search Trees.
with Tian Luo, and David P. Woodruff
ICML 2022
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra.
with Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, and David P. Woodruff
ICML 2022
Triangle and Four-Cycle Counting with Predictions in Graph Stream.
with Justin Chen, Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner,
David P. Woodruff, and Michael Zhang
ICLR 2022
Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time.
with Yu Cheng
ICLR 2021
Learning-Augmented Data Stream Algorithms.
with Tanqiu Jiang, Yi Li, Yisong Ruan, and David P. Woodruff
ICLR 2020