Samson Zhou


Hi, I'm a Postdoctoral Fellow at Carnegie Mellon University, hosted by --davidwoodruff--. My current research interests are sublinear algorithms, machine learning, and password hashing.

Previously, I was a postdoc at Indiana University hosted by --grigoryyaroslavtsev--, a postdoc at Purdue University hosted by --jeremiahblocki--, and a graduate student at Purdue University advised by --gregfrederickson-- and --elenagrigorescu--.

I try to be active occasionally and here are some of my favorite links.

You may reach me at:
samsonzhou AT gmail DOT com

Academic Positions and Education

Service and Teaching

Publications [dblp] [Scholar]

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

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

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

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

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

  6. Bandwidth-Hard Functions: Reductions and Lower Bounds
    --jeremiahblocki--, --lingren--, Samson Zhou.
    CCS 2018 [abstract] [video] [pdf]

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

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

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

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

  11. On the Economics of Offline Password Cracking
    --jeremiahblocki--, --benharsha--, Samson Zhou.
    S&P 2018 [abstract] [video] [pdf]

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

  13. On the Depth-Robustness and Cumulative Pebbling Cost of Argon2i
    --jeremiahblocki--, Samson Zhou.
    TCC 2017 [abstract] [pdf]

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

  15. Streaming Periodicity with Mismatches
    --fundaergun--, --elenagrigorescu--, --erfansadeqiazer--, Samson Zhou.
    RANDOM 2017 [abstract] [slides] [conference] [full]

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