Publications

Publications and manuscripts are listed in the reverse chronological order. All publications, except starred ones, have their authors listed in the alphabetical order of their last names as per the convention in theoretical computer science. A full list of publications can be found on my DBLP or Google Scholar pages. 

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

• EFX Exists for Three Types of Agents.*
  Vishwa Prakash HV, Pratik Ghosal, Prajakta Nimbhorkar, Nithin Varma.  Accepted to 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 to SoCG 2025.

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

• 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 . Recipient of 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).