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.

CV

Publications

(As per the convention in theoretical computer science, all publications have authors listed in the alphabetical order of last names.)

• Analyzing Massive Datasets with Missing Entries: Models and Algorithms (PhD Thesis). [Defense Slides]
  Advisor: Dr. Sofya Raskhodnikova
  Boston University.
  
  
• Average Sensitivity of Graph Algorithms. [Video] [Slides]
  Nithin Varma, Yuichi Yoshida.
  Manuscript.
  
  
• Bipartite Graphs of Small Readability. [Slides]
  Rayan Chikhi, Vladan Jovicic, Stefan Kratsch, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova, Nithin Varma.
  Theoretical Computer Science (2019).
  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