Publications

Reasoning agents Model architecture Interactive decision making Safety & privacy Information theory
α Alphabetical author order * Equal contribution

2026

  1. The Price of Hidden Curvature: Improved Lower Bounds for Bandit Convex Optimization
    N. Rajaraman and Y. Han
    🧠
    preprint
  2. Learning to Reason with Curriculum II: Compositional Generalization
    N. Rajaraman, A. Huang, M. Dudik, R. Schapire, D. Foster, and A. Krishnamurthy
    🤖 🧠
    preprint
  3. Select and Improve: Understanding the Mechanics of Post-Training for Reasoning
    A. Krishnamurthy, A. Huang, and N. Rajaraman
    🤖
    preprint
  4. Learning to Reason with Curriculum I: Provable Benefits of Autocurriculum
    N. Rajaraman, A. Huang, M. Dudik, R. Schapire, D. J. Foster, and A. Krishnamurthy
    🤖 🧠
    COLT 2026
  5. Interactive Learning of Single-Index Models via Stochastic Gradient Descent
    N. Rajaraman and Y. Han
    🧠
    ICLR 2026
  6. From Markov to Laplace: How Mamba In-context Learns Markov chains
    M. Bondaschi, N. Rajaraman, M. Gastpar, K. Ramchandran, C. Gulcehre, R. Pascanu, and A. V. Makkuva
    🧬
    ICLR 2026 (oral)

2025

  1. Scaling Test-Time Compute Without Verification or RL is Suboptimal
    A. Setlur, N. Rajaraman, S. Levine, and A. Kumar
    🤖
    ICML 2025 (spotlight)
  2. SPECS: Faster Test-Time Scaling through Speculative Drafts
    M. Cemri, N. Rajaraman, R. Tiwari, X. Liu, K. Keutzer, I. Stoica, K. Ramchandran, A. Beirami, and Z. Sun
    🤖
    NeurIPS 2027; ICML 2025 Workshop on Efficient Systems for Foundation Models (ES-FOMO III)
  3. Computational Intractability of Strategizing against Online Learners
    A. Assosᵅ, Y. Daganᵅ, and N. Rajaramanᵅ
    COLT 2025
  4. The Space Complexity of Learning Unlearning Algorithms
    Y. Cherapanamjeriᵅ, S. Gargᵅ, N. Rajaramanᵅ, A. Sekhariᵅ, and A. Shettyᵅ
    🔐
    COLT 2025

2024

  1. An Analysis of Tokenization: Transformers under Markov Data
    N. Rajaraman, J. Jiao, and K. Ramchandran
    🧬
    NeurIPS 2024 (spotlight)
  2. Transformers on Markov data: Constant depth suffices
    N. Rajaraman, M. Bondaschi, A. V. Makkuva, K. Ramchandran, and M. Gastpar
    🧬
    Neurips 2024; ICML 2024 Workshop on Mechanistic Interpretability 2024

2023

  1. Statistical complexity and optimal algorithms for non-linear ridge bandits
    N. Rajaraman, Y. Han, J. Jiao, and K. Ramchandran
    🧠
    Annals of Statistics
  2. Greedy pruning with group lasso provably generalizes for matrix sensing
    N. Rajaraman, Devvrit, A. Mokhtari, and K. Ramchandran
    NeurIPS 2023

2022

  1. Sample efficient deep reinforcement learning via local planning
    D. Yin, S. Thiagarajan, N. Lazic, N. Rajaraman, B. Hao, and C. Szepesvari
    🧠
    preprint
  2. Minimax optimal online imitation learning via replay estimation
    G. Swamy*, N. Rajaraman*, M. Peng, S. Choudhury, J. Bagnell, S. Z. Wu, J. Jiao, and K. Ramchandran
    🧠
    NeurIPS 2022
    Code
  3. Semi-supervised active linear regression
    N. Rajaraman, Devvrit, and P. Awasthi
    🧠
    NeurIPS 2022
  4. Spectral regularization allows data-frugal learning over combinatorial spaces
    A. Aghazadeh, N. Rajaraman, T. Tu, and K. Ramchandran
    TMLR
    Code

2021

  1. On the value of interaction and function approximation in imitation learning
    N. Rajaraman, Y. Han, L. Yang, J. Liu, J. Jiao, and K. Ramchandran
    🧠
    NeurIPS 2021
  2. Not just age but age and quality of information
    N. Rajaraman, R. Vaze, and G. Reddy
    📊
    IEEE Journal on Selected Areas in Communications 39 (5), 1325–1338
  3. Provably breaking the quadratic error compounding barrier in imitation learning, optimally
    N. Rajaraman, Y. Han, L. F. Yang, K. Ramchandran, and J. Jiao
    🧠
    preprint

2020

  1. Towards the fundamental limits of imitation learning
    N. Rajaraman, L. F. Yang, J. Jiao, and K. Ramchandran
    🧠
    NeurIPS 2020
  2. FastSecAgg: Scalable Secure Aggregation for Privacy-preserving Federated Learning
    S. Kadhe, N. Rajaraman, O. O. Koyluoglu, and K. Ramchandran
    🔐
    ICML Workshop on FL for User Privacy and Data Confidentiality (2020); CCS Workshop on Privacy-Preserving Machine Learning in Practice (2020); ISIT (2021)
  3. Missing Mass of Markov Chains
    P. Chandra, A. Thangaraj, and N. Rajaraman
    📊
    ISIT 2020

2019

  1. Robust correlation clustering
    R. Krishnaswamyᵅ, Devvrit*ᵅ, and N. Rajaraman*ᵅ
    APPROX/RANDOM 2019
  2. Convergence of Chao unseen species estimator
    N. Rajaraman, P. Chandra, A. Thangaraj, and A. T. Suresh
    📊
    ISIT 2019