10 citations · 25 across the 10 of their papers we have counts for
16 papers
Separations between Combinatorial Measures for Transitive Functions
Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar
The role of symmetry in Boolean functions has been extensively studied in complexity theory. For example, symmetric functions, that is, functions that are…
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…
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…
Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions
Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu +2
The Fourier-Entropy Influence (FEI) Conjecture states that for any Boolean function , the Fourier entropy of is at most its influence up to a unive…
The Balanced Connected Subgraph Problem
Sujoy Bhore, Sourav Chakraborty, Satyabrata Jana +3
The problem of computing induced subgraphs that satisfy some specified restrictions arises in various applications of graph algorithms and has been well studied. In this paper, we…
Maximal and maximum transitive relation contained in a given binary relation
Sourav Chakraborty, Shamik Ghosh, Nitesh Jha +1
We study the problem of finding a \textit{maximal} transitive relation contained in a given binary relation. Given a binary relation of size defined on a set of size , we pr…