Sai Soumya Nalli

About Me

I am currently woking with Dr Amit Deshpande as a Research Fellow at Microsoft Research India on alignment and preference learning. I completed my B.Tech from IIT Madras (CSE) in July 2024, working in the Theory Group under Prof. Jayalal Sarma on complexity theory, more specifically Boolean function complexity. I am broadly interested in theoretical computer science and more recently, have been exploring problems in theoretical machine learning.

Research

Publications

• Sensitivity and Query Complexity under Uncertainty
  Deepu Benson^†, Balagopal Komarath^†, Nikhil Mande^†, Sai Soumya Nalli^†, Jayalal Sarma^†, Karteek Sreenivasiah^†
  MFCS 2025 Find slides here
  

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 Workshop LLM Reasoning
• 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 2025 ARLET 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 (and OR) 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 in alphabetical order (common practice in theoretical computer science)