Parallel and Distributed Computing

• Overlay Network Construction: Improved Overall and Node-Wise Message Complexity
  (with Yi-Jun Chang and Yanyu Chen)
  To appear in the 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2025

• The Complexity Landscape of Dynamic Distributed Subgraph Finding
  (with Yi-Jun Chang, Lyuting Chen, Yanyu Chen, and Mingyang Yang)
  To appear in the 39th International Symposium on Distributed Computing (DISC), 2025
  Brief Announcement: 44th ACM Symposium on Principles of Distributed Computing (PODC), 2025

• Round and Communication Efficient Graph Coloring
  (with Yi-Jun Chang, Thuan Hung Nguyen, and Farrel D. Salim)
  44th ACM Symposium on Principles of Distributed Computing (PODC), 2025

• Optimal Distributed Replacement Path
  (with Yi-Jun Chang, Yanyu Chen, Dipan Dey, Thuan Hung Nguyen, and Bryce Sanchez)
  44th ACM Symposium on Principles of Distributed Computing (PODC), 2025

• A Tight Lower Bound for 3-Coloring Grids in the Online-Local Model
  (with Yi-Jun Chang, Thuan Hung Nguyen, Mingyang Yang, and Yu-Cheng Yeh)
  43rd ACM Symposium on Principles of Distributed Computing (PODC), 2024

• Streaming Graph Algorithms in the Massively Parallel Computation Model
  (with Artur Czumaj and Anish Mukherjee)
  43rd ACM Symposium on Principles of Distributed Computing (PODC), 2024

• Log Diameter Rounds MST Verification and Sensitivity in MPC
  (with Sam Coy, Artur Czumaj, and Anish Mukherjee)
  Algorithmica, accepted 2025
  36th Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024

• Parallel Derandomization for Coloring
  (with Sam Coy, Artur Czumaj, and Peter Davies)
  38th IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2024
  Highlights of Parallel Computing (HOPC), 2024

• Optimal (degree+1)-List Coloring in the Congested Clique
  (with Sam Coy, Artur Czumaj, and Peter Davies)
  SIAM Journal on Computing (SICOMP), accepted 2026
  49th EATCS International Colloquium on Automata, Languages, and Programming (ICALP), 2023

• On k-Center Clustering in MPC
  (with Sam Coy and Artur Czumaj)
  Transactions on Algorithms (TALG), accepted 2026
  Highlights of Algorithms (HALG), 2023
  35th Symposium on Parallelism in Algorithms and Architectures (SPAA), 2023

Distribution Testing

• Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
  (with Sourav Chakraborty, Eldar Fischer, Amit Levi, Arijit Ghosh, and Sayantan Sen)
  57th Annual ACM Symposium on Theory of Computing (STOC), 2024
  Featured in Oded Goldreich’s Choices

• Testing of Index-Invariant Properties in the Huge Object Model
  (with Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, and Sayantan Sen)
  36th Annual Conference on Learning Theory (COLT), 2023
  Featured in Oded Goldreich’s Choices

• Exploring the Gap between Tolerant and Non-Tolerant Distribution Testing
  (with Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, and Sayantan Sen)
  IEEE Transactions on Information Theory (TOIT), 2025
  Highlights of Algorithms (HALG), 2023
  26th International Conference on Randomization and Computation (RANDOM), 2022
  
  

Sublinear Algorithms

• Arboricity and Random Edge Queries Matter for Triangle Counting Using Sublinear Queries
  (with Arijit Bishnu and Debarshi Chanda)

• Near Uniform Triangle Sampling Over Adjacency List Graph Streams
  (with Arijit Bishnu, Arijit Ghosh, and Sayantan Sen)

• Faster Counting and Sampling Algorithms Using a Colorful Decision Oracle
  (with Anup Bhattacharya, Arijit Bishnu, and Arijit Ghosh)
  ACM Transactions on Computation Theory (TOCT), 2024
  Highlights of Algorithms (HALG), 2022
  International Symposium on Theoretical Aspects in Computer Science (STACS), 2022
  Featured in Oded Goldreich’s Choices

• Complexity of Triangle Counting Using Emptiness Queries
  (with Arijit Bishnu and Arijit Ghosh)
  27th International Conference on Randomization and Computation (RANDOM), 2023

• Counting and Sampling from Substructures Using Linear Algebraic Queries
  (with Arijit Bishnu, Arijit Ghosh, and Manaswi Paraashar)
  42nd Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2022

• Tolerant Bipartite Testing in Dense Graphs
  (with Arijit Ghosh, Rahul Raychaudhury, and Sayantan Sen)
  Highlights of Algorithms (HALG), 2023
  49th EATCS International Colloquium on Automata, Languages, and Programming (ICALP), 2022

• Sublinear-Time Algorithm for Matrix Distance Using Projections on the Hamming Cube
  (with Arijit Bishnu and Arijit Ghosh)
  International Conference on Randomization and Computation (RANDOM), 2021

• Interplay between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds
  (with Sourav Chakraborty, Arijit Ghosh, and Sayantan Sen)
  Highlights of Algorithms (HALG), 2022
  International Conference on Randomization and Computation (RANDOM), 2021
  Poster at Workshop on Local Algorithms (WOLA), 2021

• Query Complexity of Global Minimum Cut
  (with Arijit Bishnu, Arijit Ghosh, and Manaswi Paraashar)
  International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2021

• Even the Easiest Graph Coloring Problem Is Not Easy in Streaming
  (with Anup Bhattacharya, Arijit Bishnu, and Anannya Upasana)
  Innovations in Theoretical Computer Science Conference (ITCS), 2021

• Disjointness through the Lens of Vapnik–Chervonenkis Dimension
  (with Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, and Manaswi Paraashar)
  Computational Complexity (CC), 2022
  International Conference on Randomization and Computation (RANDOM), 2020

• Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams
  (with Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, and Saket Saurabh)
  Theory of Computing Systems (TOCS), 2023
  International Computing and Combinatorics Conference (COCOON), 2020
  Journal version titled: Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams

• Hyperedge Estimation Using Polylogarithmic Subset Queries
  (with Anup Bhattacharya, Arijit Bishnu, and Arijit Ghosh)

• On the Streaming Complexity of Fundamental Geometric Problems
  (with Arijit Bishnu, Arijit Ghosh, and Sandeep Sen)
  
  

Others (Metric Embedding, Graph Theory, and Combinatorial Geometry)

• Grid Obstacle Representation of Graphs
  (with Arijit Bishnu, Arijit Ghosh, Rogers Mathew, and Subhabrata Paul)
  Discrete Applied Mathematics (DAM), 2020
  Poster at International Symposium on Graph Drawing and Network Visualization (GD), 2017

• Existence of Planar Support for Geometric Hypergraphs Using Elementary Techniques
  (with Arijit Bishnu, Sameer Desai, Arijit Ghosh, and Subhabrata Paul)
  Discrete Mathematics (DM), 2020

• FPT Algorithms for Embedding into Low-Complexity Graphic Metrics
  (with Arijit Ghosh and Sudeshna Kolay)
  ACM Transactions on Computation Theory (TOCT), 2020
  European Symposium on Algorithms (ESA), 2018

• Improved Algorithms for Evacuation Route Planning Problem
  (with Subhra Mazumdar and Arindam Pal)
  Journal of Combinatorial Optimization (JCO), 2018
  Conference on Combinatorial Optimization and Applications (COCOA), 2015