Samson Zhou

Hi, I'm a Postdoctoral Researcher at Carnegie Mellon University, hosted by --davidwoodruff--. 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 high-dimensional probability. 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

Service and Teaching



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

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

  3. Non-Adaptive Adaptive Sampling on Turnstile Streams
    --sepidehmahabadi--, --ilyarazenshteyn--, --davidwoodruff--, Samson Zhou
    STOC 2020 [abstract] [Sepideh's slides] [Sepideh's video@TCS+] [pdf]

  4. "Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack
    --grigoryyaroslavtsev--, Samson Zhou, --dmitriiavdiukhin--
    AISTATS 2020 [abstract] [pdf]

  5. Data-Independent Neural Pruning via Coresets
    --benmussay--, --margaritaosadchy--, --vladimirbraverman--, Samson Zhou, --danfeldman--
    ICLR 2020 [abstract] [pdf]

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

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

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

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

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

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

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

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

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

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

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

  17. Relaxed Locally Correctable Codes in Computationally Bounded Channels
    --jeremiahblocki--, --venkatagandikota--, --elenagrigorescu--, Samson Zhou
    ISIT 2019 [abstract] [pdf]
    ICALP 2018 (brief announcement)

  18. Periodicity in Data Streams with Wildcards
    --fundaergun--, --elenagrigorescu--, --erfansadeqiazer--, Samson Zhou
    CSR 2018 (invited to special issue of Theory of Computing) [abstract] [pdf]

  19. On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling
    --jeremiahblocki--, Samson Zhou
    FC 2018 [abstract] [slides] [pdf]

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

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

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

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

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

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

Other Writings