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
    --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