Research Areas

• Algorithms & Theory

Research Interests

• Theoretical Computer Science; more specifically, algorithms on large data set, streaming algorithms, string matching algorithms, graph algorithms and data structures

Profile

Dr Diptarka CHAKRABORTY is an assistant professor in the Department of Computer Science. He obtained his PhD degree in Computer Science and Engineering from the Indian Institute of Technology Kanpur, India in 2016. After that he spent two years at Charles University, Prague, Czech Republic as a post-doctoral fellow hosted by Prof. Michal Koucky, and then almost an year at Weizmann Institute of Science, Israel as a post-doctoral fellow hosted by Prof. Robert Krauthgamer. His research interests are in the areas of Theoretical Computer Science; more specifically, algorithms on large data set, streaming algorithms, string matching algorithms, graph algorithms and data structures.

Current Projects

Selected Publications

• Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time

  Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucky and Michael Saks

  FOCS 2018 (winner of best paper award)

• Space-Optimal Quasi-Gray Codes with Logarithmic Read Complexity

  Diptarka Chakraborty, Debarati Das, Michal Koucky and Nitin Saurabh

  ESA 2018 (Track A)

• Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication

  Diptarka Chakraborty, Lior Kamma and Kasper Green Larsen

  STOC 2018 and HALG 2019

• Streaming Algorithms for Embedding and Computing Edit Distance in the Low Distance Regime

  Diptarka Chakraborty, Elazar Goldenberg and Michal Koucky

  STOC 2016 and HALG 2016

Awards & Honours

• Best Paper Award at FOCS 2018
• IBM Research India Outstanding Ph.D. Student Award 2015-16

Teaching (2019/2020)

• CS3230: Design and Analysis of Algorithms