Prantar Ghosh

About Me

I am a Lecturer in the Department of Computer Science at Dartmouth College for the Summer term. I am teaching Discrete Mathematics in Computer Science (CS30). In Fall 2022, I shall be joining DIMACS at Rutgers University as a Simons Postdoctoral Leader!

I recently completed my Ph.D. in Computer Science at Dartmouth, where I was fortunate to be advised by Amit Chakrabarti. My thesis is titled Space-Efficient Algorithms and Verification Schemes for Graph Streams.

My research interests lie broadly in Theoretical Computer Science, especially in graph algorithms. I'm currently working on designing efficient graph algorithms in memory-restricted settings such as data streaming and stream verification, as well as in the dynamic setting. I'm also interested in communication complexity, FPT algorithms, graph-query/sublinear-time algorithms, and combinatorial graph theory.

Before joining Dartmouth, I spent five wonderful years at Chennai Mathematical Institute (CMI), India, where I completed my M.Sc. in Computer Science in 2017 and B.Sc. in Mathematics and Computer Science in 2015. My Master's thesis on FPT Algorithms Using Algebraic Techniques was advised by G. Philip.

Here's a copy of my CV (as of June 2022).

Research

Profiles: Google Scholar dblp

Publications

• A New Dynamic Algorithm for Densest Subhypergraphs TheWebConf (formerly WWW) 2022
  Suman K. Bera, Sayan Bhattacharya, Jayesh Choudhari, Prantar Ghosh
  Nominated for Best Paper Award
  [full version (arXiv)] [conference version] [slides]

• Adversarially Robust Coloring for Graph Streams ITCS 2022
  Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl
  [full version (arXiv)] [conference version] [talk] [slides]

• Oriented Bipartite Graphs and the Goldbach Graph Discrete Math., Vol. 344 (9), 2021
  Sandip Das, Prantar Ghosh, Shamik Ghosh, Sagnik Sen
  [full version (arXiv)] [journal version]

• New Verification Schemes for Frequency-Based Functions on Data Streams FSTTCS 2020
  Prantar Ghosh
  [full version (arXiv)] [conference version] [talk] [slides]

• Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches RANDOM 2020
  Amit Chakrabarti, Prantar Ghosh, Justin Thaler
  [full version (arXiv)] [ECCC] [conference version] [talk] [slides]

• Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models ICALP 2020
  Suman K. Bera, Amit Chakrabarti, Prantar Ghosh
  [full version (arXiv)] [conference version] [talk] [slides]

• Vertex Ordering Problems in Directed Graph Streams SODA 2020
  Amit Chakrabarti, Prantar Ghosh, Andrew McGregor, Sofya Vorotnikova
  [full version (arXiv)] [conference version] [talk slides]

• Streaming Verification of Graph Computations via Graph Structure RANDOM 2019
  Amit Chakrabarti, Prantar Ghosh
  [full version (ECCC)] [conference version] [conference slides] [talk (workshop at Simons Institute)] [workshop slides]

• Relative Clique Number of Planar Signed Graphs CALDAM 2016
  Sandip Das, Prantar Ghosh, Swathyprabhu Mj, Sagnik Sen
  [conference version] [journal version in Discrete Appl. Math., Vol. 280, 2020]
  

Theses and Technical Reports

• Space-Efficient Algorithms and Verification Schemes for Graph Streams
  Ph.D. Thesis, Dartmouth College, 2022

• Coloring in Graph Streams ArXiv 2018
  Suman K. Bera, Prantar Ghosh
  [link]

• FPT Algorithms Using Algebraic Techniques
  Master's Thesis, Chennai Mathematical Institute, 2017

Teaching

In Summer 2022, I am teaching Discrete Mathematics in Computer Science (CS30) at Dartmouth College.

I have served as a Teaching Assistant for the following courses at Dartmouth College.

• CS31 Algorithms Spring 2021

• CS30 Discrete Mathematics in Computer Science Summer 2020

• CS35/135 Data Streaming Algorithms Spring 2020

• CS30 Discrete Mathematics in Computer Science Winter 2020

• CS31 Algorithms Spring 2019 Best TA Award

• CS30 Discrete Mathematics in Computer Science Winter 2019 (Academic Year 2018-19)

• Math76 Topics in Applied Mathematics Summer 2018

• CS31 Algorithms Spring 2018

• CS30 Discrete Mathematics in Computer Science Winter 2018

• CS01 Introduction to Programming and Computation Fall 2017

I have served as a Teaching Assistant for the following courses at Chennai Mathematical Institute.

• Discrete Mathematics Jan–Apr 2017

• Parameterized and Exact Algorithms Aug–Nov 2016

• Discrete Mathematics Jan–Apr 2016