Publications
A New Information Complexity Measure for Multi-Pass Streaming with Applications
with Mark Braverman, Qian Li, Shuo Wang, David P. Woodruff and Jiapeng Zhang
To appear in STOC 2024. [arXiv]
Oracle Efficient Online Multicalibration and Omniprediction
with Christopher Jung, Omer Reingold and Aaron Roth
SODA 2024. [arXiv]
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]