Prantar Ghosh

Mail: Campus Box 5101, Department of Computer Science, Tennessee Technological University, Cookeville, TN 38505

Office: Bruner Hall 430

Email: pghosh<at>tntech<dot>edu

About Me

I am an Assistant Professor in the Department of Computer Science at Tennessee Tech University, where I joined in Fall 2024.
Here's my university profile.

Research Interests

My research interests lie broadly in Theoretical Computer Science, the area of Computer Science that deals with its mathematical foundations. I specialize in graph algorithms and mostly study massive graphs in the streaming model of computation where the focus is to optimize the memory usage. The broad goal of my research is to understand how much memory is necessary and sufficient for solving natural problems on streaming graphs. This involves (a) designing space-efficient algorithms for the problems at hand, and (b) (unconditionally) proving their minimum space requirements.

I have also worked on a variety of other topics over the years, and my research interests include dynamic graph algorithms, communication complexity, graph-query/sublinear-time algorithms, FPT algorithms, and combinatorial graph theory.

Prospective PhD students: I am actively looking for motivated PhD students with a good mathematical background (funding for two students available). If you are interested in working with me, feel free to email me with a short summary of your background and your resume. You can also apply directly to Tennessee Tech's graduate program and mention my name in your application.

Undergraduate students: I am open to supervising undergraduate research for self-motivated students with a good mathematical background. Shoot me an email if you are interested in working with me.

Bio

Prior to joining Tennessee Tech, I spent a couple of years as a postdoc: one year at Georgetown University hosted by Justin Thaler, and another as a Simons Postdoctoral Leader at DIMACS, Rutgers University, where I primarily worked with Sepehr Assadi.

Before that, in May 2022, I completed my PhD in Computer Science at Dartmouth College, where I was fortunate to be advised by Amit Chakrabarti. Then I spent the summer of 2022 as a Lecturer in the Department of Computer Science at Dartmouth.

Before joining Dartmouth, I spent five wonderful years at Chennai Mathematical Institute (CMI), India, where I completed my Masters in Computer Science in 2017 and Bachelors in Mathematics and Computer Science in 2015.

Here's a copy of my CV (as of Jan 2025).

Research

Profiles: Google Scholar dblp

Preprints

Dynamic Algorithms for Diverse Minimum Spanning Trees
Prantar Ghosh, Mayank Goswami, Meng-Tsung Tsai

Publications

New Algorithms and Lower Bounds for Streaming Tournaments ESA 2024
Prantar Ghosh, Sahil Kuchlous
[full version (arXiv)] [conference version] [conference slides by Sahil]
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy CCC 2024
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay
[full version (arXiv)] [conference version] [slides]
Low-Memory Algorithms for Online and W-Streaming Edge Coloring ICALP 2024
Prantar Ghosh, Manuel Stoeckl
[full version (arXiv)] [conference version] [slides]
New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification ITCS 2024

Prantar Ghosh, Vihan Shah

[full version (arXiv)] [conference version] [recorded talk] [recorded talk slides] [conference slides by Vihan]

Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms PODS 2023
Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl
[full version (arXiv)] [conference version] [poster by Manuel] [conference slides by Manuel]
A New Dynamic Algorithm for Densest Subhypergraphs WWW 2022
Suman K. Bera, Sayan Bhattacharya, Jayesh Choudhari, Prantar Ghosh
Nominated for Best Paper Award
[full version (arXiv)] [conference version] [talk] [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
Suman K. Bera, Prantar Ghosh
[arXiv, 2018]

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

Students

I'm currently mentoring the following amazing undergraduate students

Sahil Kuchlous (DIMACS REU 2023 mentee)
Amirhossein Janfaza (Remote research collaboration)

Teaching

Current courses:

Spring 2025: CSC 6400: Advanced Analysis of Algorithms

Past courses:

Fall 2024: CSC 2400: Design of Algorithms
Summer 2022: CS30: Discrete Mathematics in Computer Science (lecture notes are public) at Dartmouth College.

Service

I co-organized the DIMACS Workshop on Modern Techniques in Graph Algorithms in June 2023.

I have been an external reviewer for several conferences (multiple iterations of most) including STOC, FOCS, SODA, SOSA, ICALP, APPROX, RANDOM, ESA, ITCS, FSTTCS, ISAAC, STACS.

I have been a reviewer for journals including TOCT, IPL, and OPTL.

Page updated

Google Sites

Report abuse