publications

all co-authors are listed in alphabetical order.

preprints

• Online Tokenization with Optimal Delay in Linear Time

  with Mina Dalirrooyfard

  [arXiv]

• Simple, Faster (min, +) Matrix Multiplication and APSP

  with Barna Saha

  [arXiv]

2027

• Furthest Pair Requires Quadratic Time in Superconstant Dimension under SETH

  with Barna Saha and Yinzhan Xu

  SODA 2027

  [arXiv]

• Approximate Replicability in Learning

  with Max Hopkins and Russell Impagliazzo

  SODA 2027

  [arXiv]

2026

• Almost Optimal Multiple Source Shortest Paths and Reachability

  with Barna Saha and Yinzhan Xu

  FOCS 2026

  [arXiv]

• On the Computational Hardness of Transformers

  with Barna Saha, Yinzhan Xu, and Hantao Yu

  STOC 2026

  [arXiv] [STOC]

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

  with Hadley Black

  SODA 2026

  [arXiv] [SODA]

• From Generative to Episodic: Sample-Efficient Replicable RL

  with Max Hopkins, Sihan Liu, and Yuichi Yoshida

  ICML 2026

  [arXiv] [ICML]

• Subquadratic Algorithms and Hardness for Attention with Any Temperature

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

  ICLR 2026

  [arXiv] [ICLR]

2025

• Replicable Distribution Testing

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

  NeurIPS 2025

  Selected for Spotlight Presentation

  [arXiv] [NeurIPS]

• 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]