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
As Teaching Assistant
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
- 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 (*) 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.