Sagnik Mukhopadhyay

43 papers A* 10A 4B 2Journal 25Unranked 2
YearRankTypeTitle / Venue / Authors
2026 — conf
Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs.
SOSA
Olivier Fischer, Yonggang Jiang, Sagnik Mukhopadhyay, Sorrachai Yingchareonthawornchai
2026 A* conf
Shortcuts and Transitive-Closure Spanners Approximation.
SODA
Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, Danupon Nanongkai
2025 J jnl
Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs.
CoRR
Yonggang Jiang, Sagnik Mukhopadhyay, Sorrachai Yingchareonthawornchai
2025 J jnl
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations.
CoRR
Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay, Sorrachai Yingchareonthawornchai
2025 A* conf
Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions and Near-Optimal Separations.
STOC
Joakim Blikstad, Yonggang Jiang, Sagnik Mukhopadhyay, Sorrachai Yingchareonthawornchai
2025 J jnl
Shortcuts and Transitive-Closure Spanners Approximation.
CoRR
Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, Danupon Nanongkai
2024 A conf
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy.
CCC
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay
2024 J jnl
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy.
CoRR
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay
2023 A* conf
Fast Algorithms via Dynamic-Oracle Matroids.
STOC
Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, Ta-Wei Tu
2023 J jnl
Fast Algorithms via Dynamic-Oracle Matroids.
CoRR
Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, Ta-Wei Tu
2023 A* conf
Finding a Small Vertex Cut on Distributed Networks.
STOC
Yonggang Jiang, Sagnik Mukhopadhyay
2023 J jnl
Finding a Small Vertex Cut on Distributed Networks.
CoRR
Yonggang Jiang, Sagnik Mukhopadhyay
2022 A* conf
Cut Query Algorithms with Star Contraction.
FOCS
Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
2022 J jnl
Cut query algorithms with star contraction.
CoRR
Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
2022 B conf
Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition.
IPCO
Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, Danupon Nanongkai
2022 A* conf
Nearly Optimal Communication and Query Complexity of Bipartite Matching.
FOCS
Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
2022 J jnl
Nearly Optimal Communication and Query Complexity of Bipartite Matching.
CoRR
Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
2021 J jnl
A Note on Isolating Cut Lemma for Submodular Function Minimization.
CoRR
Sagnik Mukhopadhyay, Danupon Nanongkai
2021 J jnl
Breaking the Quadratic Barrier for Matroid Intersection.
CoRR
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai
2021 A* conf
Breaking the quadratic barrier for matroid intersection.
STOC
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai
2021 A* conf
Distributed weighted min-cut in nearly-optimal time.
STOC
Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
2021 B conf
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs.
SPAA
Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai
2021 J jnl
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs.
CoRR
Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai
2020 J jnl
Distributed Weighted Min-Cut in Nearly-Optimal Time.
CoRR
Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai
2020 J jnl
Faster connectivity in low-rank hypergraphs via expander decomposition.
CoRR
Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, Danupon Nanongkai
2020 A* conf
Weighted min-cut: sequential, cut-query, and streaming algorithms.
STOC
Sagnik Mukhopadhyay, Danupon Nanongkai
2019 A conf
Lifting Theorems for Equality.
STACS
Bruno Loff, Sagnik Mukhopadhyay
2019 J jnl
Simulation Theorems via Pseudo-random Properties.
Comput. Complex.
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2019 J jnl
Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms.
CoRR
Sagnik Mukhopadhyay, Danupon Nanongkai
2018 J jnl
Lifting Theorems for Equality.
Electron. Colloquium Comput. Complex.
Bruno Loff, Sagnik Mukhopadhyay
2018 J jnl
Separation Between Deterministic and Randomized Query Complexity.
SIAM J. Comput.
Sagnik Mukhopadhyay, Jaikumar Radhakrishnan, Swagato Sanyal
2018 A* conf
Simulation beats richness: new data-structure lower bounds.
STOC
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2017 J jnl
Composition and Simulation Theorems via Pseudo-random Properties.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2017 A conf
Lower Bounds for Elimination via Weak Regularity.
STACS
Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2017 J jnl
Simulation Beats Richness: New Data-Structure Lower Bounds.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2017 J jnl
Simulation Theorems via Pseudorandom Properties.
CoRR
Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2016 J jnl
Lower Bounds for Elimination via Weak Regularity.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay
2016 J jnl
Tribes Is Hard in the Message Passing Model.
CoRR
Arkadev Chattopadhyay, Sagnik Mukhopadhyay
2016 J jnl
Tribes Is Hard in the Message Passing Model.
Electron. Colloquium Comput. Complex.
Sagnik Mukhopadhyay
2015 — conf
Towards Better Separation between Deterministic and Randomized Query Complexity.
FSTTCS
Sagnik Mukhopadhyay, Swagato Sanyal
2015 J jnl
Towards Better Separation between Deterministic and Randomized Query Complexity.
CoRR
Sagnik Mukhopadhyay, Swagato Sanyal
2015 J jnl
Towards Better Separation between Deterministic and Randomized Query Complexity.
Electron. Colloquium Comput. Complex.
Sagnik Mukhopadhyay, Swagato Sanyal
2015 A conf
Tribes Is Hard in the Message Passing Model.
STACS
Arkadev Chattopadhyay, Sagnik Mukhopadhyay