Publications

Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, Danupon Nanongkai (2023). Shortcuts and Transitive-Closure Spanners Approximation.

arXiv (Soon)

Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay (2023). Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy.

arXiv (Soon)

Yonggang Jiang, Sagnik Mukhopadhyay, Sorrachai Yingchareonthawornchai (2023). Breaking Quadratic Barriers for Vertex Connectivity: Communication, Streaming, and Quantum Edge-Query Algorithms.

arXiv (Soon)

Yonggang Jiang, Sagnik Mukhopadhyay (2023). Finding a Small Vertex Cut on Distributed Networks. In STOC 2023.

PDF Video arXiv

Joakim Blikstad, Danupon Nanongkai, Ta-Wei Tu, Sagnik Mukhopadhyay (2023). Fast Algorithms via Dynamic-Oracle Matroids. In STOC 2023.

PDF Video arXiv

Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai (2022). Nearly Optimal Communication and Query Complexity of Bipartite Matching. In FOCS 2022.

PDF arXiv

Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai (2022). Cut Query Algorithms with Star Contraction. In FOCS 2022.

PDF arXiv

Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, Danupon Nanongkai (2022). Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition. In IPCO 2022.

PDF arXiv

Sagnik Mukhopadhyay, Danupon Nanongkai (2021). A Note on Isolating Cut Lemma for Submodular Function Minimization.

PDF arXiv

Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai (2021). Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs. In SPAA 2021.

PDF Video arXiv

Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai (2021). Distributed Weighted Min-Cut in Nearly-Optimal Time. In STOC 2021.

PDF Video arXiv

Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai (2021). Breaking the Quadratic Barrier for Matroid Intersection. In STOC 2021.

PDF Video arXiv

Sagnik Mukhopadhyay, Danupon Nanongkai (2020). Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms. In STOC 2020.

PDF Slides Video arXiv

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay (2019). Simulation Theorems via Pseudo-random Properties. Computational Complexity (28:4).

PDF Cite Slides DOI

Bruno Loff, Sagnik Mukhopadhyay (2019). Lifting Theorems for Equality. In STACS 2019.

PDF Cite Slides DOI ECCC

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay (2018). Simulation Beats Richness: New Data-Structure Lower Bounds. In STOC 2018.

PDF Cite Slides Video DOI ECCC

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay (2017). Lower Bounds for Elimination via Weak Regularity. In STACS 2017.

PDF Cite Video DOI DOI

Sagnik Mukhopadhyay, Swagato Sanyal, Jaikumar Radhakrishnan (2015). Separation between Deterministic and Randomized Query Complexity. SIAM Journal on Computing (47:4).

PDF Cite DOI

Arkadev Chattopadhyay, Sagnik Mukhopadhyay (2015). Tribes is Hard in Message-passing Model. In STACS 2015.

PDF Cite Slides DOI arXiv

Sagnik Mukhopadhyay, Swagato Sanyal (2015). Towards Better Separation between Deterministic and Randomized Query Complexity. In FSTTCS 2015.

PDF Cite Slides DOI arXiv