Parallel and Distributed Computing
Overlay Network Construction: Improved Overall and Node-Wise Message Complexity
(with Yi-Jun Chang and Yanyu Chen)
[ArXiv]
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
[ArXiv]
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
[ArXiv]
Optimal Distributed Replacement Path
(with Yi-Jun Chang, Yanyu Chen, Dipan Dey, Thuan Hung Nguyen, Bryce Sanchez)
44th ACM Symposium on Principles of Distributed Computing (PODC), 2025
[ArXiv]
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 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), 2025
Parallel Derandomization for Coloring
(with Sam Coy, Artur Czumaj, and Peter Davies)
38th IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2024
Highlights of Parallel Computing (HOPC), 2024
Optimal (degree+1)-List Coloring in Congested Clique
(with Sam Coy, Artur Czumaj, and Peter Davies)
49th EATCS International Colloquium on Automata, Languages, and Programming (ICALP), 2023
On k-Center clustering in MPC
(with Sam Coy and Artur Czumaj)
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
[ArXiv, ECCC][Conference Version]
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, 2025.
Highlights of Algorithms (HALG), 2023
26th International Conference on Randomization and Computation (RANDOM), 2022
[ArXiv][Conference Version][Journal Version]
Sublinear Algorithms.
Arboricity and Random Edge Queries Matter for Triangle Counting Using Sublinear Queries
(with Arjjit Bishnu and Debarshi Chanda)
[ArXiv]
Near Uniform Triangle Sampling Over Adjacency List Graph Streams
(with Arijit Bishnu, Arijit Ghosh, and Sayantan Sen)
[ArXiv]
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
Proc. Int. Symphosium on Theoratical Aspects in Computer Science (STACS), 2022
[ArXiv][Conference Version][Journal Version]
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
The 49th EATCS International Colloquium on Automata, Languages, and Programming (ICALP), 2022
Sublinear-Time Algorithm for Matrix Distance using Projections on Hamming Cube
(with Arijit Bishnu and Arijit Ghosh)
Proc. Int. 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
Poster at Workshop on Local Algorithms (WOLA), 2021
Proc. Int. Conference on Randomization and Computation (RANDOM), 2021
[ECCC][Conference Version]
Query Complexity of Global Minimum Cut
(with Arijit Bishnu, Arijit Ghosh, and Manaswi Paraashar)
Proc. Int. Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2021
[ECCC, ArXiv][Conference Version]
Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming
(with Anup Bhattacharya, Arijit Bishnu, and Anannya Upasana)
Proc. Innovations in Theoretical Computer Science Conference (ITCS), 2021
Disjointness through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond
(with Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, and Manaswi Paraashar)
Computational Complexity (CC), 2022
Proc. Int. Conference on Randomization and Computation (RANDOM), 2020
[ECCC, ArXiv][Conference Version][Journal Version]
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
Proc. International Computing and Combinatorics Conference (COCOON), 2020
[ArXiv][Conference Version][Journal Version]
Note: The journal version appears as "Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams."
On Triangle Estimation using Tripartite Independent Set Queries
(with Anup Bhattacharya, Arijit Bishnu, and Arijit Ghosh)
Theory of Computing Systems (TOCS), 2021
Proc. Int. Symp. on Algorithms and Computation (ISAAC), 2019
[ArXiv][Conference Version][Journal Version]
Parameterized Query Complexity of Hitting Set using Stability of Sunflowers
(with Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, and Saket Saurabh)
Journal of Computer and System Sciences (JCSS), 2023
Proc. Int. Symp. on Algorithms and Computation (ISAAC), 2018
[ArXiv][Conference Version][Journal Version]
Note: The journal version appears as "Almost optimal query algorithm for hitting set using a subset query."
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 in Proc. Int. Symp. on Graph Drawing & Network Visualization (GD), 2017
[ArXiv][Journal Version]
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
Proc. European Symposium on Algorithms (ESA), 2018
[ArXiv][Conference Version][Jounal Version]
Improved Algorithms for Evacuation Route Planning Problem
(with Subhra Mazumdar and Arindam pal)
Journal of Combinatorial Optimization (JOCO), 2018
Proc. Conference on Combinatorial Optimization and Applications (COCOA), 2015
[ArXiv][Conference Version][Journal Version]
Manuscripts
Hyperedge Estimation using Polylogarithmic Subset Queries
with Anup Bhattacharya, Arijit Bishnu, and Arijit Ghosh
[ArXiv]
On the Streaming Complexity of Fundamental Geometric Problems
with Arijit Bishnu, Arijit Ghosh, and Sandeep Sen
[ArXiv]