Nithin Varma

Assistant Professor, Computer Science
Chennai Mathematical Institute, India

My research is in the field of Algorithms, with a focus on Sublinear-time algorithms, Randomized algorithms and Approximation algorithms.

Before joining CMI, I completed my postdoc at the Department of Computer Science, University of Haifa, Israel, where I was working with Dr. Ilan Newman and Dr. Noga Ron-Zewi. I did my Ph.D. from Boston University in 2019 and consider myself fortunate to have been advised by Dr. Sofya Raskhodnikova. The first three years (2014 - 2017) of my PhD were done while I was a graduate student at Penn State (advised by Dr. Sofya Raskhodnikova). I obtained my Master's degree (2011 - 2014) from TIFR Mumbai, where I was advised by Dr. Kavitha Telikepalli. I got my B.Tech. degree (2007 - 2011) in Computer Science and Engineering from National Institute of Technology, Calicut, where I was advised by Dr. K. Muralikrishnan.

Teaching

• ALGO Design and Analysis of Algorithms, Course co-teaching with G. Philip, Jan-May 2023
  
• COMM Communication Complexity, Course co-taught with Prajakta Nimbhorkar, Aug-Nov 2022
  
• ALGO Design and Analysis of Algorithms, Course co-taught with G. Philip, Jan-May 2022
  
• AALG Approximation Algorithms, Course co-taught with Pranabendu Mishra, Jan-May 2022
  
• ALGO Design and Analysis of Algorithms, Course co-taught with Prajakta Nimbhorkar, Sep-Dec 2021
  
• ADAL Advanced Algorithms, Course co-taught with Prajakta Nimbhorkar, Sep-Dec 2021 (covering Sublinear Algorithms in the second half)

As Teaching Assistant

• CS 530 Advanced Algorithms, Boston University, Fall 2018
• CS 537 Randomness in Computing, Boston University, Spring 2018
• CSE 565 Algorithm Design and Analysis, Penn State, Fall 2016
  

Outreach

• Something for Almost Nothing: A Gentle Introduction to Sublinear Algorithms (Slides)
  Invited expert lecture at (1) Computer Science Department, NIT Calicut India, September 2022, (2) KREA University, January 2023.


• How to multiply numbers fast? (Slides)
  Invited popular science lecture by National Academy of Sciences, India, July 2022.


• Introduction to Matrix Algorithms, Weeklong course at Raising a Mathematician Foundation co-taught with Kavita Sutar, May 2022
  Topics : Gaussian Elimination, LU Decomposition, Karatsuba's Integer Multiplication Algorithm, Strassen's Matrix Multiplication Algorithm,
  Frievald's Algorithm for Verifying Matrix Multiplication.


• Concise communication: A computer science perspective (Slides)
  Invited outreach talk at Raising a Mathematician Foundation.

Publications

(As per the convention in theoretical computer science, all publications have authors listed in the alphabetical order of last names.)

• Strongly Sublinear-Time Algorithms for Testing Pattern Freeness. [Slides]
  Ilan Newman and Nithin Varma.
  Best Paper at ICALP 2022 [ICALP Talk Slides].
  
  
• Sublinear-Time Computation in the Presence of Online Erasures.
  Iden Kalemaj, Sofya Raskhodnikova and Nithin Varma.
  ITCS 2022: 90:1-90:25
  A full version is available on arXiv.
  
  
• Parameterized Convexity Testing.[Slides]
  Abhiruk Lahiri, Ilan Newman and Nithin Varma.
  Accepted to SOSA 2022.

• Erasures vs. Errors in Local Decoding and Property Testing. [Slides] [Poster]
  Sofya Raskhodnikova, Noga Ron-Zewi, 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. [Video of talk at ICALP '21] [Slides]
  Ilan Newman and Nithin Varma.
  A preliminary version appeared in the proceedings of ICALP 2021.

• Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (even for Small Rate and Huge Lists). [Video of talk at ITCS '21] [Slides]
  Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma.
  A preliminary version appeared in the proceedings of ITCS 2021.

• Erasure-Resilient Sublinear-Time Graph Algorithms. [Video of talk at ITCS '21] [Slides]
  Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma.
  A preliminary version appeared in the proceedings of ITCS 2021.
  Full version accepted to ACM Transactions on Computation Theory.
  
  
• Average Sensitivity of Graph Algorithms. [Video of talk at WoLA '20] [Slides]
  Nithin Varma, Yuichi Yoshida.
  A preliminary version appeared in the proceedings of SODA 2021.
  
  
• Analyzing Massive Datasets with Missing Entries: Models and Algorithms (PhD Thesis). [Defense Slides]
  Advisor: Dr. Sofya Raskhodnikova
  Boston University.
  
  
• 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.
  
  
• Brief Announcement: Erasure-Resilience versus Tolerance to Errors.
  Sofya Raskhodnikova, Nithin Varma.
  ICALP 2018, 111:1-111:3.

• Erasure-Resilient Property Testing.
  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.
  Telikepalli Kavitha, Nithin Varma.
  SIAM Journal of Discrete Mathematics 29(4): 2239-2254 (2015).
  A preliminary version appeared in the proceedings of ICALP 2013.
  


• Small Stretch Pairwise Spanners and D-spanners (Master's Thesis). [Slides]
  Advisor: Dr. Kavitha Telikepalli
  Tata Institute of Fundamental Research, Mumbai, India.


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

Talks

• Strongly Sublinear Algorithms for Testing Pattern Freeness
  Talk at (*) Algorithms and Complexity Seminar, IISc Bangalore (*) ICALP 2022 (*) MIT Seminar on Local Algorithms (*) Rutgers and DIMACS Theory Seminar (*) CMI Chennai Theory Seminar.

• Parameterized Convexity Testing
  Talk at (*) SOSA 2022.

• New Algorithms and Lower Bounds for LIS Estimation
  Talk at (*) ICALP 2021 (*) MIT Local Algorithms Seminar (*) Boston University Algorithms and Theory Seminar.

• Query Complexity Lower Bounds for Local List Decoding
  Talk at (*) ITCS 2021.

• Erasure-Resilient Sublinear-Time Graph Algorithms
  Talk at (*) Mondays with Marty, U Haifa (*) Portland State University (*) ITCS 2021.

• Average Sensitivity of Graph Algorithms (Slides)
  Talk at (*) CS Theory Seminar, Technion, Israel, (*) Workshop on Local Algorithms 2020 (*) SODA 2021 (*) HALG 2021.
  
  
• Separating Errors and Erasures in Property Testing using Local List Decoding (Slides)
  Talk at (*) CS Theory Seminar, John Hopkins Univ., (*) CS Algo. and Theory Seminar, Boston University, (*) CS Seminar, UC Santa Cruz, (*) CS Theory Seminar, Dartmouth College, (*) ITCS 2019.
  
  
• Brief Announcement: Erasure-Resilience versus Tolerance to Errors (Slides)
  Talk at (*) ICALP 2018.
   
• Bipartite Graphs of Small Readability (Slides)
  Talk at (*) COCOON 2018.
  
  
• Erasure-Resilient Graph Property Testing
  Talk at (*) WoLA 2018.
  
  
• Erasure-Resilient Property Testing (Slides used in the IITM Talk)
  Talks at (*) MIT, (*) Northeastern University, (*) Univ. Michigan, Ann Arbor, (*) IIT Madras, India, (*) IBM Research, TJ Watson, (*) Microsoft Research, Bangalore, (*) Indian Institute of Science, Bangalore, (*) ICALP 2016, (*) HALG 2016. 


• Fast and Fault-Resilient Sublinear Algorithms (Slides)
  Talk at (*) Boston University.


• Small Stretch Pairwise Spanners and D-spanners (Slides)
  Talks at (*) CSE Theory Seminar, Penn State, (*) TIFR, Mumbai, (*) ICALP 2013. 

Posters

• Erasures vs. Errors in Local Decoding and Property Testing ITCS 2019.
• Fast and Fault-Resilient Sublinear Algorithms BU CS Day, 2017.
  
• Erasure-Resilient Property Testing WoLa 2016, HALG 2016, MIT Sublinear Day 2015, DIMACS Big Data Workshop 2015.

Contact Info

• Email : nithinvarma ? cmi ? ac ? in
  Insert appropriate characters in the email address above.