Sagnik Mukhopadhyay

According to our database, Sagnik Mukhopadhyay authored at least 21 papers between 2015 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy.

Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Finding a Small Vertex Cut on Distributed Networks.

Yonggang Jiang, Sagnik Mukhopadhyay

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Fast Algorithms via Dynamic-Oracle Matroids.

Joakim Blikstad, Sagnik Mukhopadhyay, Danupon Nanongkai, Ta-Wei Tu

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022

Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition.

Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, Danupon Nanongkai

Proceedings of the Integer Programming and Combinatorial Optimization, 2022

Nearly Optimal Communication and Query Complexity of Bipartite Matching.

Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Cut Query Algorithms with Star Contraction.

Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

A Note on Isolating Cut Lemma for Submodular Function Minimization.

Sagnik Mukhopadhyay, Danupon Nanongkai

CoRR, 2021

Distributed weighted min-cut in nearly-optimal time.

Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Breaking the quadratic barrier for matroid intersection.

Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs.

Andrés López-Martínez, Sagnik Mukhopadhyay, Danupon Nanongkai

Proceedings of the SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, 2021

2020

Weighted min-cut: sequential, cut-query, and streaming algorithms.

Sagnik Mukhopadhyay, Danupon Nanongkai

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Simulation Theorems via Pseudo-random Properties.

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Comput. Complex., 2019

2018

Separation Between Deterministic and Randomized Query Complexity.

Sagnik Mukhopadhyay, Jaikumar Radhakrishnan, Swagato Sanyal

SIAM J. Comput., 2018

Lifting Theorems for Equality.

Bruno Loff, Sagnik Mukhopadhyay

Electron. Colloquium Comput. Complex., 2018

2017

Simulation Beats Richness: New Data-Structure Lower Bounds.

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Electron. Colloquium Comput. Complex., 2017

Composition and Simulation Theorems via Pseudo-random Properties.

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Electron. Colloquium Comput. Complex., 2017

Simulation Theorems via Pseudorandom Properties.

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

CoRR, 2017

2016

Tribes Is Hard in the Message Passing Model.

Sagnik Mukhopadhyay

Electron. Colloquium Comput. Complex., 2016

Lower Bounds for Elimination via Weak Regularity.

Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay

Electron. Colloquium Comput. Complex., 2016

2015

Towards Better Separation between Deterministic and Randomized Query Complexity.

Sagnik Mukhopadhyay, Swagato Sanyal

Electron. Colloquium Comput. Complex., 2015

Tribes Is Hard in the Message Passing Model.

Arkadev Chattopadhyay, Sagnik Mukhopadhyay

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015