Sagnik Mukhopadhyay

Publication Activity (10 Years)

Years Active: 2015-2024
Publications (10 Years): 33

Top Topics

Query Complexity

Top Venues

Electron. Colloquium Comput. Complex.

Publications

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