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

• New Sublinear Algorithms and Lower Bounds for LIS Estimation. [Slides]
  Ilan Newman and Nithin Varma.

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

• 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, 91:1-91:15.

• Parameterized Property Testing of Functions.
  Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma.
  ACM TOCT 9(4): 17:1-17:19 (2018).
  A preliminary version appeared in the proceedings of ITCS 2017, 12:1-12:17.


• Small Stretch Pairwise Spanners and Approximate D-preservers.
  Telikepalli Kavitha, Nithin Varma.
  SIAM Journal of Discrete Math. 29(4): 2239-2254 (2015).
  A preliminary version appeared in the proceedings of ICALP (1) 2013: 601-612.
  


• 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 Maths 38: 239-244 (2011).

Teaching

• CS 530 Advanced Algorithms
  Teaching Fellow, Fall 2018, Boston University.

• CS 537 Randomness in Computing
  Teaching Assistant, Spring 2018, Boston University.

• CSE 565 Algorithm Design and Analysis
  Teaching Assistant, Fall 2016, Penn State.

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

• 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 : nvarma "at" bu "dot" edu