Nithin Varma
Postdoctoral Researcher
I am a postdoc working with Dr.
Ilan Newman and Dr.
Noga Ron-Zewi at the Department
of Computer Science, University
of Haifa, Israel. My research is in the field of Algorithms, with a
focus on Sublinear-time algorithms, Randomized algorithms, and Graph
algorithms.
I completed 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).
Before joining Penn State, 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.
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.
- 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, 467-479.
- Erasures
vs. Errors in Local Decoding and Property Testing.
[Slides] [Poster]
Sofya Raskhodnikova, Noga
Ron-Zewi, Nithin Varma.
ITCS 2019, 63:1-63:21.
A full version is
available on ECCC.
- Brief
Announcement: Erasure-Resilience versus Tolerance to Errors.
Sofya Raskhodnikova, Nithin Varma.
ICALP 2018, 111:1-111:3.
Teaching
Talks
- New Algorithms and Lower Bounds for LIS Estimation
Talk at (*) 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.
- 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 : nvarma "at" bu "dot" edu