Recent Preprints
The Structure of In-Place Space-Bounded Computation. [ECCC-TR25-150]
with James Cook, Surendra Ghentiyala, Ian Mertz, and Nathan Sheffield.
Composing Low Space Algorithms. [ECCC-TR25-140] [Oded's Choices]
with Roei Tell.
Efficient Catalytic Graph Algorithms. [arXiv:2509.06209]
with James Cook.
To Appear
Collapsing Catalytic Classes. [ECCC-TR25-019]
with Michal Koucký, Ian Mertz, and Sasha Sami.
FOCS 2025.
Publications
A Fast Coloring Oracle for Average Case Hypergraphs. [arXiv:2507.10691]
with Cassandra Marcussen, Ronitt Rubinfeld, Asaf Shapira and Shlomo Tauber.
RANDOM 2025.
The Structure of Catalytic Space: Capturing Randomness and Time Via Compression. [ECCC-TR24-106]
with James Cook, Jiatu Li, and Ian Mertz.
STOC 2025.
When Connectivity is Hard, Random Walks are Easy With Non-Determinism. [ECCC-TR25-077]
with Dean Doron, Roei Tell, and Ryan Williams.
STOC 2025.
Catalytic Communication. [ECCC-TR24-188]
with Nathan Sheffield and William Wang.
ITCS 2025.
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness. [ECCC-TR24-139]
with Jiatu Li and Roei Tell.
FOCS 2024.
Derandomizing Logspace With a Small Shared Hard Drive. [ECCC-TR23-168]
CCC 2024. Invited to special issue of Computational Complexity.
Best Student Paper.
Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL. [ECCC-TR23-208] [Brown Seminar]
STOC 2024.
with Dean Doron and Roei Tell.
Pseudorandom Linear Codes are List-Decodable to Capacity. [arXiv:2303.17554]
ITCS 2024.
with Aaron (Louie) Putterman.
Certified Hardness vs. Randomness for Logspace. [ECCC-TR23-040]
FOCS 2023.
with Ran Raz and Wei Zhan.
Singular Value Approximation and Sparsifying Random Walks on Directed Graphs. [arXiv:2301.13541]
FOCS 2023.
with AmirMahdi Ahmadinejad, John Peebles, Aaron Sidford, and Salil Vadhan.
Improved Local Computation Algorithms for Constructing Spanners. [arXiv:2105.04847v2]
RANDOM 2023.
with Rubi Arviv, Lily Chung, and Reut Levi.
On the Power of Regular and Permutation Branching Programs. [ECCC-TR23-102] [Oded's Choices]
RANDOM 2023.
with Chin Ho Lee and Salil Vadhan.
Near-Optimal Derandomization of Medium-Width Branching Programs. [ECCC-TR22-150]
STOC 2023.
with Aaron (Louie) Putterman.
See also concurrent work (STOC 2023) by Cohen, Doron, Sberlo, and Ta-Shma.
Fourier Growth of Regular Branching Programs. [ECCC-TR22-034]
RANDOM 2022.
with Chin Ho Lee and Salil Vadhan.
Hitting Sets for Regular Branching Programs. [ECCC-TR21-143]
CCC 2022.
with Andrej Bogdanov, William Hoza, and Gautam Prakriya.
Deterministic Approximation of Random Walks via Queries in Graphs of Unbounded Size. [arXiv:2111.01997]
SOSA 2022.
with Salil Vadhan.
Limitations of the Impagliazzo–Nisan–Wigderson Pseudorandom Generator against Permutation Branching Programs. [ECCC-TR21-108]
Algorithmica.
with Willian Hoza and Salil Vadhan.
Local Access to Random Walks. [arXiv:2102.07740] [ITCS Talk] [Property Testing Review]
ITCS 2022.
with Amartya Shankha Biswas and Ronitt Rubinfeld.
Pseudodistributions That Beat All Pseudorandom Generators. [ECCC-TR21-019] [CCC Talk] [Oded's Choices]
CCC 2021. Invited to special issue of Theory of Computing.
with Salil Vadhan.
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs. [ECCC-TR20-138] [ITCS Talk] [Oded's Choices]
ITCS 2021.
with William Hoza and Salil Vadhan.
Old(er) Preprints
A Study of Error Reduction Polynomials. [ECCC-TR24-090]
with Gil Cohen, Dean Doron, Tomer Manket, Yichuan Wang, and Tal Yankovitz.