Sliding window order statistics in sublinear space. - Dhruv Rohatgi (CoRR, 2018)

Conditional Hardness of Earth Mover Distance. - Dhruv Rohatgi (APPROX-RANDOM, 2019)

Off-Diagonal Ordered Ramsey Numbers of Matchings. - Dhruv Rohatgi (Electron. J. Comb., 2019)

Truncated Linear Regression in High Dimensions. - Constantinos Daskalakis; Dhruv Rohatgi; Emmanouil Zampetakis (NeurIPS, 2020)

Constant-Expansion Suffices for Compressed Sensing with Generative Priors. - Constantinos Daskalakis; Dhruv Rohatgi; Emmanouil Zampetakis (NeurIPS, 2020)

Near-Optimal Bounds for Online Caching with Machine Learned Advice. - Dhruv Rohatgi (SODA, 2020)

On the Power of Preconditioning in Sparse Linear Regression. - Jonathan A. Kelner; Frederic Koehler; Raghu Meka; Dhruv Rohatgi (FOCS, 2021)

Regarding Two Conjectures on Clique and Biclique Partitions. - Dhruv Rohatgi; John C. Urschel; Jake Wellens (Electron. J. Comb., 2021)

Learning in Observable POMDPs, without Computationally Intractable Oracles. - Noah Golowich; Ankur Moitra; Dhruv Rohatgi (NeurIPS, 2022)

Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs. - Jonathan A. Kelner; Frederic Koehler; Raghu Meka; Dhruv Rohatgi (NeurIPS, 2022)

Robust Generalized Method of Moments: A Finite Sample Viewpoint. - Dhruv Rohatgi; Vasilis Syrgkanis (NeurIPS, 2022)

Planning in Observable POMDPs in Quasipolynomial Time. - Noah Golowich; Ankur Moitra; Dhruv Rohatgi (CoRR, 2022)

Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs. - Jonathan A. Kelner; Frederic Koehler; Raghu Meka; Dhruv Rohatgi (CoRR, 2022)

Provably Auditing Ordinary Least Squares in Low Dimensions. - Ankur Moitra; Dhruv Rohatgi (ICLR, 2023)

Feature Adaptation for Sparse Linear Regression. - Jonathan A. Kelner; Frederic Koehler; Raghu Meka; Dhruv Rohatgi (NeurIPS, 2023)

Provable benefits of score matching. - Chirag Pabbaraju; Dhruv Rohatgi; Anish Prasad Sevekari; Holden Lee; Ankur Moitra; Andrej Risteski (NeurIPS, 2023)

Planning and Learning in Partially Observable Systems via Filter Stability. - Noah Golowich; Ankur Moitra; Dhruv Rohatgi (STOC, 2023)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps. - Jonathan A. Kelner; Frederic Koehler; Raghu Meka; Dhruv Rohatgi (COLT, 2024)

Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning. - Noah Golowich; Ankur Moitra; Dhruv Rohatgi (FOCS, 2024)

Online Control in Population Dynamics. - Noah Golowich; Elad Hazan; Zhou Lu; Dhruv Rohatgi; Y. Jennifer Sun (NeurIPS, 2024)

Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles. - Noah Golowich; Ankur Moitra; Dhruv Rohatgi (STOC, 2024)

On Learning Parities with Dependent Noise. - Noah Golowich; Ankur Moitra; Dhruv Rohatgi (CoRR, 2024)

Towards characterizing the value of edge embeddings in Graph Neural Networks. - Dhruv Rohatgi; Tanya Marwah; Zachary Chase Lipton; Jianfeng Lu 001; Ankur Moitra; Andrej Risteski (CoRR, 2024)

Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration. - Dylan J. Foster; Zakaria Mhammedi; Dhruv Rohatgi (COLT, 2025)

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification (extended abstract). - Dhruv Rohatgi; Adam Block; Audrey Huang; Akshay Krishnamurthy; Dylan J. Foster (COLT, 2025)

Necessary and Sufficient Oracles: Toward a Computational Taxonomy for Reinforcement Learning. - Dhruv Rohatgi; Dylan J. Foster (COLT, 2025)

Self-Improvement in Language Models: The Sharpening Mechanism. - Audrey Huang; Adam Block; Dylan J. Foster; Dhruv Rohatgi; Cyril Zhang; Max Simchowitz; Jordan T. Ash; Akshay Krishnamurthy (ICLR, 2025)

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification. - Dhruv Rohatgi; Adam Block; Audrey Huang; Akshay Krishnamurthy; Dylan J. Foster (CoRR, 2025)