Publications
A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
with Jabari Hastings, Chirag Pabbaraju and Vatsal Sharan
To appear in STOC 2026. [paper available soon]
Query Lower Bounds for Correlation Clustering under Memory Constraints
with Songhua He and Periklis A. Papakonstantinou
ITCS 2026. [paper available soon]
Online Learning with Limited Information in the Sliding Window Model
with Vladimir Braverman, Chen Wang, David P. Woodruff, Samson Zhou
SODA 2026. [arXiv]
Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes
with Akash K. Sengupta
FOCS 2025. [ECCC]
The Space Complexity of Learning-Unlearning Algorithms
with Yeshwanth Cherapanamjeri, Nived Rajaraman, Ayush Sekhari and Abhishek Shetty
COLT 2025. [arXiv]
Testing Tensor Products of Algebraic Codes
with Madhu Sudan and Gabriel Wu
RANDOM 2025. [arXiv]. Invited to the ToC Special Issue for APPROX/RANDOM 2025
A New Information Complexity Measure for Multi-Pass Streaming with Applications
with Mark Braverman, Qian Li, Shuo Wang, David P. Woodruff and Jiapeng Zhang
STOC 2024. [arXiv]
Oracle Efficient Online Multicalibration and Omniprediction
with Christopher Jung, Omer Reingold and Aaron Roth
SODA 2024. [arXiv][Talk at IAS (1hr)]
Tight Space Complexity of the Coin Problem
with Mark Braverman and Or Zamir
FOCS 2021. [ECCC] [12 min talk]
Memory-Sample Lower Bounds for Learning Parity with Noise
with Pravesh K. Kothari, Pengda Liu and Ran Raz
RANDOM 2021. [arXiv]
The Coin Problem with Applications to Data Streams
with Mark Braverman and David P. Woodruff
FOCS 2020. [ECCC] [TCS+ Talk (1 hr)] [slides]
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG
with Pravesh K. Kothari and Ran Raz
RANDOM 2020. [arXiv] [20 min talk]
The Role of Randomness and Noise in Strategic Classification
with Mark Braverman
Learning in Presence of Strategic Behavior Workshop at EC 2019.
FORC 2020. [arXiv] [20 min talk]
Tracking and Improving Information in the Service of Fairness
with Michael P. Kim and Omer Reingold
EC 2019. [arXiv] [Michael's talk]
Time-Space Lower Bounds for Two-Pass Learning
with Ran Raz and Avishay Tal
The Space Complexity of Mirror Games
with Jon Schneider
ITCS 2019. [arXiv]
Pseudorandom Pseudo-Distributions with Near-Optimal Error for Read-Once Branching Programs
with Mark Braverman and Gil Cohen
STOC 2018. [ECCC] [Talk from 1:40-2:25 at STOC 2021 Workshop]
SIAM Journal on Computing [Link]. Invited to the SICOMP Special Issue for STOC 2018
Extractor-Based Time-Space Lower Bounds for Learning
with Ran Raz and Avishay Tal
STOC 2018. [ECCC] [Talk at IAS (1 hr)] [slides]
Network Coding in Undirected Graphs is either very helpful or not helpful at all
with Mark Braverman and Ariel Schvartzman
Invited Paper
New Security Notions and Feasibility Results for Authentication of Quantum Data
with Henry Yuen and Mark Zhandry
QCrypt 2016. Crypto 2017. [arXiv]