Nithin Varma
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
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.)
- 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.
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
Contact Info
- Email : nithinvarma ? cmi ? ac ? in
Insert appropriate characters in the email address above.