Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Post-doc in theoretical computer science
Verified email at kth.se - Homepage
Title
Cited by
Cited by
Year
Simulation theorems via pseudo-random properties
A Chattopadhyay, M Koucký, B Loff, S Mukhopadhyay
computational complexity 28 (4), 617-659, 2019
262019
Weighted min-cut: sequential, cut-query, and streaming algorithms
S Mukhopadhyay, D Nanongkai
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing …, 2020
202020
Simulation beats richness: New data-structure lower bounds
A Chattopadhyay, M Koucký, B Loff, S Mukhopadhyay
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing …, 2018
152018
Towards better separation between deterministic and randomized query complexity
S Mukhopadhyay, S Sanyal
arXiv preprint arXiv:1506.06399, 2015
112015
Lifting theorems for equality
B Loff, S Mukhopadhyay
36th International Symposium on Theoretical Aspects of Computer Science …, 2019
102019
Tribes is hard in the message passing model
A Chattopadhyay, S Mukhopadhyay
arXiv preprint arXiv:1602.06079, 2016
102016
Composition and Simulation Theorems via Pseudo-random Properties.
A Chattopadhyay, M Koucký, B Loff, S Mukhopadhyay
Electronic Colloquium on Computational Complexity (ECCC) 24, 14, 2017
82017
Lower bounds for elimination via weak regularity
A Chattopadhyay, P Dvorák, M Koucký, B Loff, S Mukhopadhyay
LIPIcs-Leibniz International Proceedings in Informatics 66, 2017
42017
Distributed Weighted Min-Cut in Nearly-Optimal Time
M Dory, Y Efron, S Mukhopadhyay, D Nanongkai
arXiv preprint arXiv:2004.09129, 2020
22020
Lifting Theorems for Equality.
S Mukhopadhyay, B Loff
STACS 2019, 36th International Symposium on Theoretical Aspects of Computer …, 2019
22019
Lifting Theorems for Equality.
S Mukhopadhyay, B Loff
STACS 2019, 36th International Symposium on Theoretical Aspects of Computer …, 2019
22019
Balanced bipartitioning of a multi-weighted hypergraph for heterogeneous FPGAS
S Mukhopadhyay, P Banerjee, S Sur-Kolay
2011 VII Southern Conference on Programmable Logic (SPL), 91-96, 2011
12011
A Note on Isolating Cut Lemma for Submodular Function Minimization
S Mukhopadhyay, D Nanongkai
arXiv preprint arXiv:2103.15724, 2021
2021
Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs
A López-Martínez, S Mukhopadhyay, D Nanongkai
arXiv preprint arXiv:2102.06565, 2021
2021
Breaking the Quadratic Barrier for Matroid Intersection
J Blikstad, J Brand, S Mukhopadhyay, D Nanongkai
arXiv preprint arXiv:2102.05548, 2021
2021
Faster connectivity in low-rank hypergraphs via expander decomposition
C Beideman, K Chandrasekaran, S Mukhopadhyay, D Nanongkai
arXiv preprint arXiv:2011.08097, 2020
2020
STOC 2018-Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing.-Сер. STOC 2018-Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
M Bläser, G Jindal, C Ikenmeyer, V Lysikov, Z Allen-Zhu, A Garg, Y Li, ...
Simulation 44, 50, 2018
2018
Separation Between Deterministic and Randomized Query Complexity
S Mukhopadhyay, J Radhakrishnan, S Sanyal
SIAM Journal on Computing 47 (4), 1644-1666, 2018
2018
Communication Complexity Amplification by Function Composition
S Mukhopadhyay
Tata Institute of Fundamental Research, Mumbai, 2017
2017
A Survey on Uniform Hardness Amplification in NP
S Mukhopadhyay
Tata Institute of Fundamental Research, 2013
2013
The system can't perform the operation now. Try again later.
Articles 1–20