4 papers
Tight Chang's-lemma-type bounds for Boolean functions
Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal +3
Chang's lemma (Duke Mathematical Journal, 2002) is a classical result with applications across several areas in mathematics and computer science. For a Boolean function that ta…
Query Complexity of Global Minimum Cut
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra +1
In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, wh…
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh +2
The disjointness problem - where Alice and Bob are given two subsets of and they have to check if their sets intersect - is a central problem in the world of comm…
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead
Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande +1
Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function and the two-party bounded-erro…