Sagnik Mukhopadhyay

Orcid: 0000-0002-3722-4679

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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy.
Proceedings of the 39th Computational Complexity Conference, 2024

2023
Finding a Small Vertex Cut on Distributed Networks.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Fast Algorithms via Dynamic-Oracle Matroids.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022
Faster Connectivity in Low-Rank Hypergraphs via Expander Decomposition.
Proceedings of the Integer Programming and Combinatorial Optimization, 2022

Nearly Optimal Communication and Query Complexity of Bipartite Matching.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Cut Query Algorithms with Star Contraction.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021
A Note on Isolating Cut Lemma for Submodular Function Minimization.
CoRR, 2021

Distributed weighted min-cut in nearly-optimal time.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Breaking the quadratic barrier for matroid intersection.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs.
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.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019
Simulation Theorems via Pseudo-random Properties.
Comput. Complex., 2019

2018
Separation Between Deterministic and Randomized Query Complexity.
SIAM J. Comput., 2018

Lifting Theorems for Equality.
Electron. Colloquium Comput. Complex., 2018

2017
Simulation Beats Richness: New Data-Structure Lower Bounds.
Electron. Colloquium Comput. Complex., 2017

Composition and Simulation Theorems via Pseudo-random Properties.
Electron. Colloquium Comput. Complex., 2017

Simulation Theorems via Pseudorandom Properties.
CoRR, 2017

2016
Tribes Is Hard in the Message Passing Model.
Electron. Colloquium Comput. Complex., 2016

Lower Bounds for Elimination via Weak Regularity.
Electron. Colloquium Comput. Complex., 2016

2015
Towards Better Separation between Deterministic and Randomized Query Complexity.
Electron. Colloquium Comput. Complex., 2015

Tribes Is Hard in the Message Passing Model.
Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015


  Loading...