Nithin Varma

Postdoctoral Researcher

I am a postdoc working with with Dr. Ilan Newman 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 from National Institute of Technology, Calicut, where I was advised by Dr. K. Muralikrishnan.

I am in the job market for faculty positions starting in Fall 2021.

CV

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.
  Ilan Newman and Nithin Varma.

• Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (even for Small Rate and Huge Lists).
  Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma.
  Accepted to ITCS 2021.

• Sublinear Algorithms for Graphs with Incomplete Information.
  Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma.
  Accepted to ITCS 2021.
  
  
• Average Sensitivity of Graph Algorithms. [Video] [Slides]
  Nithin Varma, Yuichi Yoshida.
  Accepted to 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).
  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).
  

Posters

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

Talks

• Average Sensitivity of Graph Algorithms (Slides)
  Talk at (*) CS Theory Seminar, Technion, Israel, (*) Workshop on Local Algorithms 2020.
  
  
• 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)
  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. 

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.
  

Contact Info

• Email : nvarma "at" bu "dot" edu