Publications

Testing Forbidden Order Patterns over Hypergrids.
Harish Chandramouleeswaran, Ilan Newman, Tomer Pelleg, Nithin Varma. Accepted to SODA 2026.

Towards Better-than-2 Approximation for Constrained Correlation Clustering.
Andreas Kalavas, Evangelos Kipouridis, Nithin Varma. ICML 2025. Spotlight Poster.

EFX Exists for Three Types of Agents.*
Vishwa Prakash HV, Pratik Ghosal, Prajakta Nimbhorkar, Nithin Varma.  EC 2025.

Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions.
Martin Herold, Danupon Na Nongkai, Joachim Spoerhaase, Nithin Varma, Zihang Wu.
A preliminary version appeared in the proceedings of SoCG 2025.

(Almost Full) EFX for Three (and More) Types of Agents.
Vishwa Prakash HV, Pratik Ghosal, Prajakta Nimbhorkar, Nithin Varma.  AAAI 2025.
Oral Presentation (top 4% of submitted papers). 

Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists).
Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma.
Accepted to Theory of Computing.
A preliminary version appeared in the proceedings of ITCS 2021. 

Strongly Sublinear-Time Algorithms for Testing Pattern Freeness. [Slides][Slides of ICALP Talk]
Ilan Newman and Nithin Varma.
TheoretiCS, Volume 3, Article 1, pp. 1-39, 2024.  
A preliminary version appeared in the proceedings of ICALP 2022 . Best Paper Award.

Average Sensitivity of Graph Algorithms. [Slides]
Nithin Varma and Yuichi Yoshida.
SIAM Journal on Computing, 52(4), pp. 1039-1081, 2023.
A preliminary version appeared in the proceedings of SODA 2021. 

Sublinear-Time Computation in the presence of Online Erasures.
Iden Kalemaj, Sofya Raskhodnikova and Nithin Varma.
Theory of Computing, Volume 19 (1), pp. 1–48, 2023.
A preliminary version appeared in the proceedings of ITCS 2022.

Erasure-Resilient Sublinear-Time Graph Algorithms. [Slides]
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova and Nithin Varma.
ACM Transactions on Computation Theory 14(1). 1:1-1:22, 2022.
A preliminary version appeared in the proceedings of ITCS 2021.

Parameterized Convexity Testing. [Slides]
Abhiruk Lahiri, Ilan Newman, Nithin Varma. SOSA 2022: 174 - 181.

Erasures vs. Errors in Local Decoding and Property Testing. [Slides] [Poster]
Sofya Raskhodnikova, Noga Ron-Zewi and Nithin Varma.
Random Structures and Algorithms 59: 640–670, 2021.
A preliminary version appeared in the proceedings of ITCS 2019.

New Sublinear Algorithms and Lower Bounds for LIS Estimation. [Slides]
Ilan Newman and Nithin Varma. ICALP 2021: 100:1 - 100:20.

Bipartite Graphs of Small Readability. [Slides]
Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma.
Theoretical Computer Science. 806: 402-415, 2020.
A preliminary version appeared in the proceedings of COCOON 2018. 

Erasure-Resilient Property Testing. [Slides]
Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma.
SIAM Journal on Computing. 47(2): 295-329, 2018.
A preliminary version appeared in the proceedings of ICALP 2016. 

Parameterized Property Testing of Functions.
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma.
ACM Transactions on Computation Theory 9(4): 17:1-17:19, 2018.
A preliminary version appeared in the proceedings of ITCS 2017.

Small Stretch Pairwise Spanners and Approximate D-Preservers. [Slides]
Telikepalli Kavitha, Nithin Varma.
SIAM Journal on Discrete Math. 29(4): 2239-2254, 2015.
A preliminary version appeared in the proceedings of ICALP 2013.

Rainbow connection number and connected dominating sets.
L. Sunil Chandran, Anita Das, Deepak Rajendraprasad, Nithin Varma.
Journal of Graph Theory 71(2): 206-218 (2012).
A preliminary version appeared in the Electronic Notes in Discrete Mathematics 38: 239-244 (2011).