My research is in the field of Algorithms,
with a focus on Sublinear-time algorithms, Randomized algorithms and
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.
As Teaching Assistant
- Introduction to Matrix Algorithms, Short 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.
(As per the convention in theoretical computer science, all
publications have authors listed in the alphabetical order of last names.)
Sublinear-Time Graph Algorithms. [Video of talk at ITCS '21] [Slides]
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin
version appeared in the proceedings of ITCS
Full version accepted to ACM Transactions
on Computation Theory.
Sensitivity of Graph Algorithms. [Video of talk at WoLA '20] [Slides]
Nithin Varma, Yuichi
version appeared in the proceedings of SODA
- Analyzing Massive Datasets with
Missing Entries: Models and Algorithms (PhD Thesis). [Defense
Advisor: Dr. Sofya Raskhodnikova
Graphs of Small Readability. [Slides]
Rayan Chikhi, Vladan Jovicic, Stefan
Kratsch, Paul Medvedev, Martin Milanic,
Sofya Raskhodnikova, Nithin Varma.
Theoretical Computer Science 806:
version appeared in the proceedings of COCOON
Announcement: Erasure-Resilience versus Tolerance to Errors.
Sofya Raskhodnikova, Nithin Varma.
ICALP 2018, 111:1-111:3.
- Strongly Sublinear Algorithms for Testing Pattern Freeness
Talk at (*) 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
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
- Email : nithinvarma ? cmi ? ac ? in
Insert appropriate characters in the email address above.