publications

all co-authors are listed in alphabetical order.

Preprints

From Generative to Episodic: Sample-Efficient Replicable RL

with Max Hopkins, Sihan Liu, and Yuichi Yoshida

[arXiv]

Subquadratic Algorithms and Hardness for Attention with Any Temperature

with Shreya Gupta, Boyang Huang, Barna Saha, and Yinzhan Xu

[arXiv]

2026

Distribution Testing in the Presence of Arbitrarily Dominant Noise with Verification Queries

with Hadley Black

SODA 2026

[arXiv]

2025

Replicable Distribution Testing

with Ilias Diakonikolas, Jingyi Gao, Daniel Kane, and Sihan Liu

NeurIPS 2025

Selected for Spotlight Presentation

[arXiv]

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence

with Jakob Nogler, Adam Polak, Barna Saha, Virginia Vassilevska Williams, and Yinzhan Xu

STOC 2025

[arXiv] [STOC]

The Computational Complexity of Factored Graphs

with Shreya Gupta, Boyang Huang, Russell Impagliazzo, and Stanley Woo

ITCS 2025

[arXiv] [ITCS]

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More

with Barna Saha, Virginia Vassilevska Williams, and Yinzhan Xu

SODA 2025

[arXiv] [SODA]

2024

Replicable Uniformity Testing

with Sihan Liu

NeurIPS 2024

[arXiv] [NeurIPS]

Replicability in High Dimensional Statistics

with Max Hopkins, Russell Impagliazzo, Daniel Kane, and Sihan Liu

FOCS 2024

[arXiv] [FOCS]

I/O Complexity of Attention, or How Optimal is FlashAttention?

with Barna Saha

ICML 2024

Selected for Oral Presentation

[arXiv] [ICML]

On the Complexity of Algorithms with Prediction for Dynamic Graph Problems

with Monika Henzinger, Barna Saha, and Martin Seybold

ITCS 2024

[arXiv] [ITCS]

Faster Approximate All Pairs Shortest Paths

with Barna Saha

SODA 2024

[arXiv] [SODA]