Samson Zhou

Hi, I'm an Assistant Professor in the Department of Computer Science & Engineering at Texas A&M University. My research lies at the intersections of theoretical computer science, data science, and machine learning. In particular, I am currently interested in numerical linear algebra, streaming algorithms, and differential privacy. Here are some of my favorite links.

Profiles: [dblp] [Scholar]
Feel free to reach me at:
samsonzhou AT gmail DOT com


Academic Positions and Education


Teaching

Research Group

Service


Publications

  1. Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
    David P. Woodruff, Samson Zhou
    NeurIPS 2024 [abstract]

  2. On Socially Fair Low-Rank Approximation and Column Subset Selection
    Zhao Song, Ali Vakilian, David P. Woodruff, Samson Zhou
    NeurIPS 2024 [abstract]

  3. A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches
    Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou
    FOCS 2024 [abstract] [pdf]

  4. Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
    Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyễn, Kunal Talwar, Samson Zhou
    ICML 2024 [abstract] [pdf]

  5. Streaming Algorithms with Few State Changes
    Rajesh Jayaram, David P. Woodruff, Samson Zhou
    PODS 2024 [abstract] [pdf]

  6. Near-Optimal k-Clustering in the Sliding Window Model
    David P. Woodruff, Peilin Zhong, Samson Zhou
    NeurIPS 2023 [abstract] [poster] [pdf]

  7. Streaming Algorithms for Learning with Experts: Deterministic Versus Robust
    David P. Woodruff, Fred Zhang, Samson Zhou
    NeurIPS 2023 [abstract] [pdf]

  8. Streaming Euclidean k-median and k-means with o(log n) Space
    Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
    FOCS 2023 [abstract] [video] [slides] [pdf]

  9. How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity
    Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee, Samson Zhou
    RANDOM 2023 [abstract] [pdf]

  10. Private Data Stream Analysis for Universal Symmetric Norm Estimation
    Vladimir Braverman, Joel Manning, Zhiwei Steven Wu, Samson Zhou
    RANDOM 2023 [abstract] [slides] [pdf]
    FORC 2022 (non-archival track)

  11. Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization
    Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou
    ICML 2023 [abstract] [pdf]

  12. Provable Data Subset Selection For Efficient Neural Network Training
    Murad Tukan, Samson Zhou, Alaa Maalouf, Daniela Rus, Vladimir Braverman, Dan Feldman
    ICML 2023 [abstract] [pdf]

  13. Differentially Private Aggregation via Imperfect Shuffling
    Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, Samson Zhou
    ITC 2023 [abstract] [pdf]
    FORC 2023 (non-archival track)

  14. Selective Experience Replay Compression using Coresets for Lifelong Deep Reinforcement Learning in Medical Imaging
    Guangyao Zheng, Samson Zhou, Vladimir Braverman, Michael A. Jacobs, Vishwa S. Parekh
    MIDL 2023 [abstract] [pdf]

  15. On Differential Privacy and Adaptive Data Analysis with Bounded Space
    Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou
    EUROCRYPT 2023 [abstract] [slides] [pdf]

  16. Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation
    Ainesh Bakshi, Praneeth Kacham, Piotr Indyk, Sandeep Silwal, Samson Zhou
    ICLR 2023 (selected for spotlight presentation) [abstract] [pdf]

  17. Differentially Private L2-Heavy Hitters in the Sliding Window Model
    Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee, Samson Zhou
    ICLR 2023 (selected for spotlight presentation) [abstract] [pdf]

  18. Robust Algorithms on Adaptive Inputs from Bounded Adversaries
    Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou
    ICLR 2023 [abstract] [pdf]

  19. Near-Linear Sample Complexity for Lp Polynomial Regression
    Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou
    SODA 2023 [abstract] [slides] [pdf]

  20. Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
    Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou
    SODA 2023 [abstract] [pdf]

  21. Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
    Elena Grigorescu, Young-San Lin, Sandeep Silwal, Maoyuan Song, Samson Zhou
    NeurIPS 2022 [abstract] [pdf]

  22. Adaptive Sketches for Robust Regression with Importance Sampling
    Sepideh Mahabadi, David P. Woodruff, Samson Zhou
    RANDOM 2022 [abstract] [pdf]

  23. Hardness and Algorithms for Robust and Sparse Optimization
    Eric Price, Sandeep Silwal, Samson Zhou
    ICML 2022 [abstract] [pdf]

  24. The White-Box Adversarial Data Stream Model
    Miklós Ajtai, Vladimir Braverman, T.S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou
    PODS 2022 [abstract] [pdf]

  25. Memory Bounds for the Experts Problem
    Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou
    STOC 2022 [abstract] [slides] [video] [pdf]

  26. Learning-Augmented k-means Clustering
    Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou
    ICLR 2022 (selected for spotlight presentation) [abstract] [slides] [pdf]

  27. Fast Regression for Structured Inputs
    Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou
    ICLR 2022 [abstract] [pdf]

  28. New Coresets for Projective Clustering and Applications
    Murad Tukan, Xuan Wu, Samson Zhou, Vladimir Braverman, Dan Feldman
    AISTATS 2022 [abstract] [pdf]

  29. A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World
    Agniva Chowdhury, Aritra Bose, Samson Zhou, David P. Woodruff, Petros Drineas
    RECOMB 2022 [abstract] [pdf]

  30. Noisy Boolean Hidden Matching with Applications
    Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou
    ITCS 2022 [abstract] [video] [pdf]

  31. Truly Perfect Samplers for Data Streams and Sliding Windows
    Rajesh Jayaram, David P. Woodruff, Samson Zhou
    PODS 2022 [abstract] [pdf]

  32. Adversarial Robustness of Streaming Algorithms through Importance Sampling
    Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, Samson Zhou
    NeurIPS 2021 [abstract] [poster] [pdf]
    AdvML @ ICML 2021 (selected for oral presentation)
    Silver Best Paper Award at AdvML @ ICML 2021

  33. Dimensionality Reduction for Wasserstein Barycenter
    Zachary Izzo, Sandeep Silwal, Samson Zhou
    NeurIPS 2021 [abstract] [pdf]

  34. Efficient Coreset Constructions via Sensitivity Sampling
    Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, Samson Zhou
    ACML 2021 [abstract] [pdf]

  35. Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
    David P. Woodruff, Samson Zhou
    FOCS 2021 [abstract] [slides] [video] [pdf]

  36. Symmetric Norm Estimation and Regression on Sliding Windows
    Vladimir Braverman, Viska Wei, Samson Zhou
    COCOON 2021 [abstract] [pdf]

  37. On the Security of Proofs of Sequential Work in a Post-Quantum World
    Jeremiah Blocki, Seunghoon Lee, Samson Zhou
    ITC 2021 [abstract] [Seunghoon's slides] [Seunghoon's video] [pdf]

  38. Separations for Estimating Large Frequency Moments on Data Streams
    David P. Woodruff, Samson Zhou
    ICALP 2021 [abstract] [slides] [video] [pdf]

  39. Learning a Latent Simplex in Input Sparsity Time
    Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou
    ICLR 2021 (selected for spotlight presentation) [abstract] [slides] [pdf]

  40. Sensitivity Analysis of the Maximum Matching Problem
    Yuichi Yoshida, Samson Zhou
    ITCS 2021 [abstract] [slides] [video] [pdf]

  41. Near Optimal Linear Algebra in the Online and Sliding Window Models
    Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou
    FOCS 2020 [abstract] [slides] [video] [pdf]

  42. On Locally Decodable Codes in Resource Bounded Channels
    Jeremiah Blocki, Shubhang Kulkarni, Samson Zhou
    ITC 2020 [abstract] [Shubhang's video@ITC] [pdf]

  43. Non-Adaptive Adaptive Sampling on Turnstile Streams
    Sepideh Mahabadi, Ilya Razenshteyn, David P. Woodruff, Samson Zhou
    STOC 2020 [abstract] [Sepideh's slides] [Sepideh's video@TCS+] [pdf]

  44. "Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack
    Grigory Yaroslavtsev, Samson Zhou, Dmitrii Avdiukhin
    AISTATS 2020 [abstract] [pdf]

  45. Data-Independent Neural Pruning via Coresets
    Ben Mussay, Margarita Osadchy, Vladimir Braverman, Samson Zhou, Dan Feldman
    IEEE Transactions on Neural Networks and Learning Systems 2021 [journal]
    ICLR 2020 [abstract] [conference]

  46. Approximating Cumulative Pebbling Cost is Unique Games Hard
    Jeremiah Blocki, Seunghoon Lee, Samson Zhou
    ITCS 2020 [abstract] [Seunghoon's poster] [Seunghoon's slides] [website] [pdf]

  47. Computationally Data-Independent Memory Hard Functions
    Mohammad Hassan Ameri, Jeremiah Blocki, Samson Zhou
    ITCS 2020 [abstract] [slides] [video] [pdf]

  48. Memory-Efficient Performance Monitoring on Programmable Switches with Lean Algorithms
    Zaoxing Liu, Samson Zhou, Ori Rottenstreich, Vladimir Braverman, Jennifer Rexford
    APoCS 2020 [abstract] [pdf]

  49. Fast Fourier Sparsity Testing
    Grigory Yaroslavtsev, Samson Zhou
    SOSA 2020 [abstract] [slides] [pdf]

  50. Approximate F2-Sketching of Valuation Functions
    Grigory Yaroslavtsev, Samson Zhou
    RANDOM 2019 [abstract] [slides] [pdf]

  51. Improved Methods on Time-Decay Streams
    Vladimir Braverman, Harry Lang, Enayat Ullah, Samson Zhou
    APPROX 2019 [abstract] [pdf]

  52. Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions
    Jeremiah Blocki, Ben Harsha, Siteng Kang, Seunghoon Lee, Lu Xing, Samson Zhou
    CRYPTO 2019 [abstract] [Jeremiah's slides] [pdf]

  53. Adversarially Robust Submodular Maximization under Knapsack Constraints
    Dmitrii Avdiukhin, Slobodan Mitrović, Grigory Yaroslavtsev, Samson Zhou
    KDD 2019 (selected for oral presentation) [abstract] [poster] [slides] [video] [pdf]

  54. Structural Results on Matching Estimation with Applications to Streaming
    Marc Bury, Elena Grigorescu, Andrew McGregor, Morteza Monemizadeh, Chris Schwiegelshohn, Sofya Vorotnikova, Samson Zhou
    Algorithmica 2019 [abstract] [pdf]

  55. Bandwidth-Hard Functions: Reductions and Lower Bounds
    Jeremiah Blocki, Ling Ren, Samson Zhou
    CCS 2018 [abstract] [Jeremiah's slides] [Jeremiah's video@CCS] [pdf]

  56. Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows
    Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou
    APPROX 2018 [abstract] [poster] [slides] [pdf]

  57. Relaxed Locally Correctable Codes in Computationally Bounded Channels
    Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, Samson Zhou
    IEEE Transactions on Information Theory 2021
    ISIT 2019 [abstract] [pdf]
    ICALP 2018 (brief announcement)

  58. Periodicity in Data Streams with Wildcards
    Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
    CSR 2018 (invited to special issue of Theory of Computing) [abstract] [pdf]

  59. On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling
    Jeremiah Blocki, Samson Zhou
    FC 2018 [abstract] [slides] [pdf]

  60. On the Economics of Offline Password Cracking
    Jeremiah Blocki, Ben Harsha, Samson Zhou
    S&P 2018 [abstract] [Jeremiah's slides] [Jeremiah's video@S&P] [pdf]

  61. Streaming for Aibohphobes: Longest Palindrome with Mismatches
    Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
    FSTTCS 2017 [abstract] [slides] [pdf]

  62. On the Depth-Robustness and Cumulative Pebbling Cost of Argon2i
    Jeremiah Blocki, Samson Zhou
    TCC 2017 [abstract] [Jeremiah's slides] [pdf]

  63. Longest Alignment with Edits in Data Streams
    Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
    Allerton 2017 [abstract] [pdf]

  64. Streaming Periodicity with Mismatches
    Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
    RANDOM 2017 [abstract] [slides] [pdf]

  65. Nearly Optimal Sparse Group Testing
    Venkata Gandikota, Elena Grigorescu, Sidharth Jaggi, Samson Zhou
    IEEE Transactions on Information Theory 2019 [journal]
    Allerton 2016 [abstract] [slides] [conference]

Other Writings