Samson Zhou

According to our database, Samson Zhou authored at least 82 papers between 2016 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Bandwidth-Hard Functions: Reductions and Lower Bounds.

Jeremiah Blocki, Peiyuan Liu, Ling Ren, Samson Zhou

J. Cryptol., June, 2024

Streaming Algorithms with Few State Changes.

Rajesh Jayaram, David P. Woodruff, Samson Zhou

Proc. ACM Manag. Data, 2024

On Approximability of ℓ₂² Min-Sum Clustering.

Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, Samson Zhou

CoRR, 2024

A Strong Separation for Adversarially Robust ℓ₀ Estimation for Linear Sketches.

Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou

CoRR, 2024

Fair Submodular Cover.

Wenjing Chen, Shuo Xing, Samson Zhou, Victoria G. Crawford

CoRR, 2024

Learning-Augmented Skip Lists.

Chunkai Fu, Jung Hoon Seo, Samson Zhou

CoRR, 2024

Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters.

David P. Woodruff, Samson Zhou

Proceedings of the Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, 2024

On Socially Fair Low-Rank Approximation and Column Subset Selection.

Zhao Song, Ali Vakilian, David P. Woodruff, Samson Zhou

Proceedings of the Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, 2024

Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages.

Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar, Samson Zhou

Proceedings of the Forty-first International Conference on Machine Learning, 2024

A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches.

Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

On Differential Privacy and Adaptive Data Analysis with Bounded Space.

Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou

IACR Cryptol. ePrint Arch., 2023

Provable Data Subset Selection For Efficient Neural Network Training.

Murad Tukan, Samson Zhou, Alaa Maalouf, Daniela Rus, Vladimir Braverman, Dan Feldman

CoRR, 2023

Streaming Algorithms for Learning with Experts: Deterministic Versus Robust.

David P. Woodruff, Fred Zhang, Samson Zhou

CoRR, 2023

Differentially Private L₂-Heavy Hitters in the Sliding Window Model.

Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee, Samson Zhou

CoRR, 2023

Near-Linear Sample Complexity for <i>L_p</i> Polynomial Regression.

Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time.

Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

On Robust Streaming for Learning with Experts: Algorithms and Lower Bounds.

David P. Woodruff, Fred Zhang, Samson Zhou

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Near-Optimal k-Clustering in the Sliding Window Model.

David P. Woodruff, Peilin Zhong, Samson Zhou

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Selective experience replay compression using coresets for lifelong deep reinforcement learning in medical imaging.

Guangyao Zheng, Samson Zhou, Vladimir Braverman, Michael A. Jacobs, Vishwa Sanjay Parekh

Proceedings of the Medical Imaging with Deep Learning, 2023

Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization.

Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou

Proceedings of the International Conference on Machine Learning, 2023

Provable Data Subset Selection For Efficient Neural Networks Training.

Murad Tukan, Samson Zhou, Alaa Maalouf, Daniela Rus, Vladimir Braverman, Dan Feldman

Proceedings of the International Conference on Machine Learning, 2023

Robust Algorithms on Adaptive Inputs from Bounded Adversaries.

Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Differentially Private $L_2$-Heavy Hitters in the Sliding Window Model.

Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee, Samson Zhou

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Subquadratic Algorithms for Kernel Matrices via Kernel Density Estimation.

Ainesh Bakshi, Piotr Indyk, Praneeth Kacham, Sandeep Silwal, Samson Zhou

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Streaming Euclidean k-median and k-means with o(log n) Space.

Vincent Cohen-Addad, David P. Woodruff, Samson Zhou

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Differentially Private Aggregation via Imperfect Shuffling.

Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, Samson Zhou

Proceedings of the 4th Conference on Information-Theoretic Cryptography, 2023

Private Data Stream Analysis for Universal Symmetric Norm Estimation.

Vladimir Braverman, Joel Manning, Zhiwei Steven Wu, Samson Zhou

Proceedings of the Approximation, 2023

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

Proceedings of the Approximation, 2023

2022

Data-Independent Structured Pruning of Neural Networks via Coresets.

Ben Mussay, Dan Feldman, Samson Zhou, Vladimir Braverman, Margarita Osadchy

IEEE Trans. Neural Networks Learn. Syst., 2022

Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation.

Ainesh Bakshi, Piotr Indyk, Praneeth Kacham, Sandeep Silwal, Samson Zhou

CoRR, 2022

Near-Linear Sample Complexity for L_p Polynomial Regression.

Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou

CoRR, 2022

Memory bounds for the experts problem.

Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

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

Proceedings of the Research in Computational Molecular Biology, 2022

Truly Perfect Samplers for Data Streams and Sliding Windows.

Rajesh Jayaram, David P. Woodruff, Samson Zhou

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

The White-Box Adversarial Data Stream Model.

Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Learning-Augmented Algorithms for Online Linear and Semidefinite Programming.

Elena Grigorescu, Young-San Lin, Sandeep Silwal, Maoyuan Song, Samson Zhou

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Noisy Boolean Hidden Matching with Applications.

Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Hardness and Algorithms for Robust and Sparse Optimization.

Eric Price, Sandeep Silwal, Samson Zhou

Proceedings of the International Conference on Machine Learning, 2022

Fast Regression for Structured Inputs.

Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou

Proceedings of the Tenth International Conference on Learning Representations, 2022

Learning-Augmented $k$-means Clustering.

Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou

Proceedings of the Tenth International Conference on Learning Representations, 2022

Adaptive Sketches for Robust Regression with Importance Sampling.

Sepideh Mahabadi, David P. Woodruff, Samson Zhou

Proceedings of the Approximation, 2022

New Coresets for Projective Clustering and Applications.

Murad Tukan, Xuan Wu, Samson Zhou, Vladimir Braverman, Dan Feldman

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Relaxed Locally Correctable Codes in Computationally Bounded Channels.

Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, Samson Zhou

IEEE Trans. Inf. Theory, 2021

Dimensionality Reduction for Wasserstein Barycenter.

Zachary Izzo, Sandeep Silwal, Samson Zhou

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Adversarial Robustness of Streaming Algorithms through Importance Sampling.

Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, Samson Zhou

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Sensitivity Analysis of the Maximum Matching Problem.

Yuichi Yoshida, Samson Zhou

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Learning a Latent Simplex in Input Sparsity Time.

Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou

Proceedings of the 9th International Conference on Learning Representations, 2021

Separations for Estimating Large Frequency Moments on Data Streams.

David P. Woodruff, Samson Zhou

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators.

David P. Woodruff, Samson Zhou

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Symmetric Norm Estimation and Regression on Sliding Windows.

Vladimir Braverman, Viska Wei, Samson Zhou

Proceedings of the Computing and Combinatorics - 27th International Conference, 2021

On the Security of Proofs of Sequential Work in a Post-Quantum World.

Jeremiah Blocki, Seunghoon Lee, Samson Zhou

Proceedings of the 2nd Conference on Information-Theoretic Cryptography, 2021

Efficient Coreset Constructions via Sensitivity Sampling.

Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, Samson Zhou

Proceedings of the Asian Conference on Machine Learning, 2021

2020

Periodicity in Data Streams with Wildcards.

Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou

Theory Comput. Syst., 2020

Approximation Algorithms for Sparse Principal Component Analysis.

Agniva Chowdhury, Petros Drineas, David P. Woodruff, Samson Zhou

CoRR, 2020

Non-adaptive adaptive sampling on turnstile streams.

Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Fast Fourier Sparsity Testing.

Grigory Yaroslavtsev, Samson Zhou

Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020

Approximating Cumulative Pebbling Cost Is Unique Games Hard.

Jeremiah Blocki, Seunghoon Lee, Samson Zhou

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Computationally Data-Independent Memory Hard Functions.

Mohammad Hassan Ameri, Jeremiah Blocki, Samson Zhou

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Data-Independent Neural Pruning via Coresets.

Ben Mussay, Margarita Osadchy, Vladimir Braverman, Samson Zhou, Dan Feldman

Proceedings of the 8th International Conference on Learning Representations, 2020

On Locally Decodable Codes in Resource Bounded Channels.

Jeremiah Blocki, Shubhang Kulkarni, Samson Zhou

Proceedings of the 1st Conference on Information-Theoretic Cryptography, 2020

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

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Memory-Efficient Performance Monitoring on Programmable Switches with Lean Algorithms.

Zaoxing Liu, Samson Zhou, Ori Rottenstreich, Vladimir Braverman, Jennifer Rexford

Proceedings of the 1st Symposium on Algorithmic Principles of Computer Systems, 2020

"Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack.

Grigory Yaroslavtsev, Samson Zhou, Dmitrii Avdiukhin

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

Nearly Optimal Sparse Group Testing.

Venkata Gandikota, Elena Grigorescu, Sidharth Jaggi, Samson Zhou

IEEE Trans. Inf. Theory, 2019

On Activation Function Coresets for Network Pruning.

Ben Mussay, Samson Zhou, Vladimir Braverman, Dan Feldman

CoRR, 2019

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

Adversarially Robust Submodular Maximization under Knapsack Constraints.

Dmitrii Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavtsev, Samson Zhou

Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019

Approximate F₂-Sketching of Valuation Functions.

Grigory Yaroslavtsev, Samson Zhou

Proceedings of the Approximation, 2019

Improved Algorithms for Time Decay Streams.

Vladimir Braverman, Harry Lang, Enayat Ullah, Samson Zhou

Proceedings of the Approximation, 2019

2018

Approximating Properties of Data Streams

Samson Zhou

PhD thesis, 2018

Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions.

Jeremiah Blocki, Benjamin Harsha, Siteng Kang, Seunghoon Lee, Lu Xing, Samson Zhou

IACR Cryptol. ePrint Arch., 2018

Bandwidth-Hard Functions: Reductions and Lower Bounds.

Jeremiah Blocki, Ling Ren, Samson Zhou

IACR Cryptol. ePrint Arch., 2018

On the Economics of Offline Password Cracking.

Jeremiah Blocki, Benjamin Harsha, Samson Zhou

Proceedings of the 2018 IEEE Symposium on Security and Privacy, 2018

Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels.

Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, Samson Zhou

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling.

Jeremiah Blocki, Samson Zhou

Proceedings of the Financial Cryptography and Data Security, 2018

Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.

Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou

Proceedings of the Approximation, 2018

2017

On the Depth-Robustness and Cumulative Pebbling Cost of Argon2i.

Jeremiah Blocki, Samson Zhou

IACR Cryptol. ePrint Arch., 2017

Optimal Parametric Search for Path and Tree Partitioning.

Greg N. Frederickson, Samson Zhou

CoRR, 2017

Streaming for Aibohphobes: Longest Palindrome with Mismatches.

Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

Streaming Periodicity with Mismatches.

Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou

Proceedings of the Approximation, 2017

Longest alignment with edits in data streams.

Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou

Proceedings of the 55th Annual Allerton Conference on Communication, 2017

2016

Estimating Weighted Matchings in o(n) Space.

Elena Grigorescu, Morteza Monemizadeh, Samson Zhou

CoRR, 2016