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.

I'm looking to hire multiple PhD students in sublinear algorithms, differential privacy, or the theoretical foundations of machine learning, starting in Fall 2025. If interested, please apply to our PhD program (deadline December 15) and contact me directly!

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
    --davidwoodruff--, Samson Zhou
    NeurIPS 2024 [abstract]

  2. On Socially Fair Low-Rank Approximation and Column Subset Selection
    --zhaosong--, --alivakilian--, --davidwoodruff--, Samson Zhou
    NeurIPS 2024 [abstract]

  3. A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches
    --elenagribelyuk--, --honghaolin--, --davidwoodruff--, --huachengyu--, Samson Zhou
    FOCS 2024 [abstract] [pdf]

  4. Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
    --hilalasi--, --vitalyfeldman--, --jelaninelson--, --huynguyen--, --kunaltalwar--, Samson Zhou
    ICML 2024 [abstract] [pdf]

  5. Streaming Algorithms with Few State Changes
    --rajeshjayaram--, --davidwoodruff--, Samson Zhou
    PODS 2024 [abstract] [pdf]

  6. Near-Optimal k-Clustering in the Sliding Window Model
    --davidwoodruff--, --peilinzhong--, Samson Zhou
    NeurIPS 2023 [abstract] [poster] [pdf]

  7. Streaming Algorithms for Learning with Experts: Deterministic Versus Robust
    --davidwoodruff--, --fredzhang--, Samson Zhou
    NeurIPS 2023 [abstract] [pdf]

  8. Streaming Euclidean k-median and k-means with o(log n) Space
    --vincentcohenaddad--, --davidwoodruff--, 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
    --jeremiahblocki--, --elenagrigorescu--, --tamalikamukherjee--, Samson Zhou
    RANDOM 2023 [abstract] [pdf]

  10. Private Data Stream Analysis for Universal Symmetric Norm Estimation
    --vladimirbraverman--, --joelmanning--, --zhiweistevenwu--, Samson Zhou
    RANDOM 2023 [abstract] [slides] [pdf]
    FORC 2022 (non-archival track)

  11. Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization
    --ameyavelingker--, --maximilianvotsch--, --davidwoodruff--, Samson Zhou
    ICML 2023 [abstract] [pdf]

  12. Provable Data Subset Selection For Efficient Neural Network Training
    --muradtukan--, Samson Zhou, --alaamaalouf--, --danielarus--, --vladimirbraverman--, --danfeldman--
    ICML 2023 [abstract] [pdf]

  13. Differentially Private Aggregation via Imperfect Shuffling
    --badihghazi--, --ravikumar--, --pasinmanurangsi--, --jelaninelson--, 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
    --guangyaozheng--, Samson Zhou, --vladimirbraverman--, --michaelajacobs--, --vishwasparekh--
    MIDL 2023 [abstract] [pdf]

  15. On Differential Privacy and Adaptive Data Analysis with Bounded Space
    --itaidinur--, --uristemmer--, --davidwoodruff--, Samson Zhou
    EUROCRYPT 2023 [abstract] [slides] [pdf]

  16. Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation
    --aineshbakshi--, --praneethkacham--, --piotrindyk--, --sandeepsilwal--, Samson Zhou
    ICLR 2023 (selected for spotlight presentation) [abstract] [pdf]

  17. Differentially Private L2-Heavy Hitters in the Sliding Window Model
    --jeremiahblocki--, --seunghoonlee--, --tamalikamukherjee--, Samson Zhou
    ICLR 2023 (selected for spotlight presentation) [abstract] [pdf]

  18. Robust Algorithms on Adaptive Inputs from Bounded Adversaries
    --yeshwanthcherapanamjeri--, --sandeepsilwal--, --davidwoodruff--, --fredzhang--, --qiuyizhang--, Samson Zhou
    ICLR 2023 [abstract] [pdf]

  19. Near-Linear Sample Complexity for Lp Polynomial Regression
    --raphaelmeyer--, --cameronmusco--, --christophermusco--, --davidwoodruff--, Samson Zhou
    SODA 2023 [abstract] [slides] [pdf]

  20. Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
    --yeshwanthcherapanamjeri--, --sandeepsilwal--, --davidwoodruff--, Samson Zhou
    SODA 2023 [abstract] [pdf]

  21. Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
    --elenagrigorescu--, --youngsanlin--, --sandeepsilwal--, --maoyuansong--, Samson Zhou
    NeurIPS 2022 [abstract] [pdf]

  22. Adaptive Sketches for Robust Regression with Importance Sampling
    --sepidehmahabadi--, --davidwoodruff--, Samson Zhou
    RANDOM 2022 [abstract] [pdf]

  23. Hardness and Algorithms for Robust and Sparse Optimization
    --ericprice--, --sandeepsilwal--, Samson Zhou
    ICML 2022 [abstract] [pdf]

  24. The White-Box Adversarial Data Stream Model
    --miklosajtai--, --vladimirbraverman--, --tsjayram--, --sandeepsilwal--, --alecsun--, --davidwoodruff--, Samson Zhou
    PODS 2022 [abstract] [pdf]

  25. Memory Bounds for the Experts Problem
    --vaidehisrinivas--, --davidwoodruff--, --ziyuxu--, Samson Zhou
    STOC 2022 [abstract] [slides] [video] [pdf]

  26. Learning-Augmented k-means Clustering
    --jonergun--, --zhilifeng--, --sandeepsilwal--, --davidwoodruff--, Samson Zhou
    ICLR 2022 (selected for spotlight presentation) [abstract] [slides] [pdf]

  27. Fast Regression for Structured Inputs
    --raphaelmeyer--, --cameronmusco--, --christophermusco--, --davidwoodruff--, Samson Zhou
    ICLR 2022 [abstract] [pdf]

  28. New Coresets for Projective Clustering and Applications
    --muradtukan--, --xuanwu--, Samson Zhou, --vladimirbraverman--, --danfeldman--
    AISTATS 2022 [abstract] [pdf]

  29. A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World
    --agnivachowdhury--, --aritrabose--, Samson Zhou, --davidwoodruff--, --petrosdrineas--
    RECOMB 2022 [abstract] [pdf]

  30. Noisy Boolean Hidden Matching with Applications
    --michaelkapralov--, --amulyamusipatla--, --jakabtardos--, --davidwoodruff--, Samson Zhou
    ITCS 2022 [abstract] [video] [pdf]

  31. Truly Perfect Samplers for Data Streams and Sliding Windows
    --rajeshjayaram--, --davidwoodruff--, Samson Zhou
    PODS 2022 [abstract] [pdf]

  32. Adversarial Robustness of Streaming Algorithms through Importance Sampling
    --vladimirbraverman--, --avinatanhassidim--, --yossimatias--, --marianoschain--, --sandeepsilwal--, 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
    --zacharyizzo--, --sandeepsilwal--, Samson Zhou
    NeurIPS 2021 [abstract] [pdf]

  34. Efficient Coreset Constructions via Sensitivity Sampling
    --vladimirbraverman--, --danfeldman--, --harrylang--, --adielstatman--, Samson Zhou
    ACML 2021 [abstract] [pdf]

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

  36. Symmetric Norm Estimation and Regression on Sliding Windows
    --vladimirbraverman--, --viskawei--, Samson Zhou
    COCOON 2021 [abstract] [pdf]

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

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

  39. Learning a Latent Simplex in Input Sparsity Time
    --aineshbakshi--, --chiranjibbhattacharyya--, --ravikannan--, --davidwoodruff--, Samson Zhou
    ICLR 2021 (selected for spotlight presentation) [abstract] [slides] [pdf]

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

  41. Near Optimal Linear Algebra in the Online and Sliding Window Models
    --vladimirbraverman--, --petrosdrineas--, --cameronmusco--, --christophermusco--, --jalajupadhyay--, --davidwoodruff--, Samson Zhou
    FOCS 2020 [abstract] [slides] [video] [pdf]

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

  43. Non-Adaptive Adaptive Sampling on Turnstile Streams
    --sepidehmahabadi--, --ilyarazenshteyn--, --davidwoodruff--, 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
    --grigoryyaroslavtsev--, Samson Zhou, --dmitriiavdiukhin--
    AISTATS 2020 [abstract] [pdf]

  45. Data-Independent Neural Pruning via Coresets
    --benmussay--, --margaritaosadchy--, --vladimirbraverman--, Samson Zhou, --danfeldman--
    IEEE Transactions on Neural Networks and Learning Systems 2021 [journal]
    ICLR 2020 [abstract] [conference]

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

  47. Computationally Data-Independent Memory Hard Functions
    --hassanameri--, --jeremiahblocki--, Samson Zhou
    ITCS 2020 [abstract] [slides] [video] [pdf]

  48. Memory-Efficient Performance Monitoring on Programmable Switches with Lean Algorithms
    --zaoxlingliu--, Samson Zhou, --orirottenstreich--, --vladimirbraverman--, --jenniferrexford--
    APoCS 2020 [abstract] [pdf]

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

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

  51. Improved Methods on Time-Decay Streams
    --vladimirbraverman--, --harrylang--, --enayatullah--, Samson Zhou
    APPROX 2019 [abstract] [pdf]

  52. Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions
    --jeremiahblocki--, --benharsha--, --sitengkang--, --seunghoonlee--, --luxing--, Samson Zhou
    CRYPTO 2019 [abstract] [Jeremiah's slides] [pdf]

  53. Adversarially Robust Submodular Maximization under Knapsack Constraints
    --dmitriiavdiukhin--, --slobodanmitrovic--, --grigoryyaroslavtsev--, Samson Zhou
    KDD 2019 (selected for oral presentation) [abstract] [poster] [slides] [video] [pdf]

  54. Structural Results on Matching Estimation with Applications to Streaming
    --marcbury--, --elenagrigorescu--, --andrewmcgregor--, --mortezamonemizadeh--, --chrisschwiegelshohn--, --sofyavorotnikova--, Samson Zhou
    Algorithmica 2019 [abstract] [pdf]

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

  56. Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows
    --vladimirbraverman--, --elenagrigorescu--, --harrylang--, --davidwoodruff--, Samson Zhou
    APPROX 2018 [abstract] [poster] [slides] [pdf]

  57. Relaxed Locally Correctable Codes in Computationally Bounded Channels
    --jeremiahblocki--, --venkatagandikota--, --elenagrigorescu--, Samson Zhou
    IEEE Transactions on Information Theory 2021
    ISIT 2019 [abstract] [pdf]
    ICALP 2018 (brief announcement)

  58. Periodicity in Data Streams with Wildcards
    --fundaergun--, --elenagrigorescu--, --erfansadeqiazer--, 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
    --jeremiahblocki--, Samson Zhou
    FC 2018 [abstract] [slides] [pdf]

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

  61. Streaming for Aibohphobes: Longest Palindrome with Mismatches
    --elenagrigorescu--, --erfansadeqiazer--, Samson Zhou
    FSTTCS 2017 [abstract] [slides] [pdf]

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

  63. Longest Alignment with Edits in Data Streams
    --elenagrigorescu--, --erfansadeqiazer--, Samson Zhou
    Allerton 2017 [abstract] [pdf]

  64. Streaming Periodicity with Mismatches
    --fundaergun--, --elenagrigorescu--, --erfansadeqiazer--, Samson Zhou
    RANDOM 2017 [abstract] [slides] [pdf]

  65. Nearly Optimal Sparse Group Testing
    --venkatagandikota--, --elenagrigorescu--, --sidharthjaggi--, Samson Zhou
    IEEE Transactions on Information Theory 2019 [journal]
    Allerton 2016 [abstract] [slides] [conference]

Other Writings