Sai Soumya Nalli

About Me

I am Sai Soumya Nalli, a Research Fellow at Microsoft Research India, working with Dr. Amit Deshpande on alignment and preference learning. I completed my B.Tech in Computer Science from IIT Madras, where I worked with Prof. Jayalal Sarma on complexity theory, particularly Boolean function complexity.

I am broadly interested in theoretical computer science and, more recently, in problems at the intersection of theory and applicative areas such as machine learning. Recently, I’ve been excited by questions around where theoretical ideas and guarantees can actually become useful in practice: whether through new theoretical models, algorithms, or ways of thinking about real systems.

I’m always happy to chat with people working on related problems, especially if you think there might be interesting connections between your work and some of my previous projects.

Research

Publications

• Bounds for Hardness Condensation in the Query Model
  Chandrima Kayal^†, Rajat Mittal^†, Sai Soumya Nalli^†, Manaswi Paraashar^†, Karthikeya Polisetty^†, Jayalal Sarma^†, Nitin Saurabh^†
  CCC 2026
• Sensitivity and Query Complexity under Uncertainty
  Deepu Benson^†, Balagopal Komarath^†, Nikhil Mande^†, Sai Soumya Nalli^†, Jayalal Sarma^†, Karteek Sreenivasiah^†
  MFCS 2025 — slides

Workshop Publications

• Improving Reachability on Reasoning Puzzles
  Sukruta Prakash Midigeshi^*, Sai Soumya Nalli^*, Utkarsh Tiwari, Amit Deshpande, Nagarajan Natarajan, Vineeth N. Balasubramanian, Amit Sharma, Gaurav Sinha
  Poster at ICLR 2026 LLM Reasoning Workshop
• Modeling Tool Use in Transformers via Computation Oracles
  Utkarsh Tiwari, Sai Soumya Nalli, Amit Deshpande
  Poster at ICLR 2026 LIT Workshop
• The Role of Preference Data and Unembeddings in the Convergence Rate of DPO
  Gayathri Chandran^*, Sai Soumya Nalli^*, Sruthi Gorantla, Amit Deshpande, Anand Louis
  Poster at NeurIPS ARLET 2025 Workshop
• Outlier-Aware Preference Optimization for Large Language Models
  Pragya Srivastava, Sai Soumya Nalli, Amit Deshpande, Amit Sharma
  Posters at ICLR 2025 BiAlign and QUESTION Workshops

Technical Reports

• On Condensation of Block Sensitivity, Certificate Complexity and the AND Decision Tree Complexity
  Sai Soumya Nalli^†, Karthikeya Polisetty^†, Jayalal Sarma^†
• Hazard-free Decision Trees
  Deepu Benson^†, Balagopal Komarath^†, Sai Soumya Nalli^†, Jayalal Sarma^†

^* Equal contribution    ^† Authors listed alphabetically

News

• Attended EDIC Open House at EPFL (March 2026)
• Presented at MFCS 2025, University of Warsaw
• Gave a T-Meet talk at IIT Madras (Aug 2025)
• Awarded Best B.Tech Project (CSE, IIT Madras)
• Joined Microsoft Research India (July 2024)

Academic Background

• B.Tech in Computer Science & Engineering, IIT Madras (2024)