6 papers
Bounds for Hardness Condensation in the Query Model
Chandrima Kayal, Rajat Mittal, Sai Soumya Nalli +4
For any Boolean function with a complexity measure having value , is it possible to restrict the function to variables while keeping t…
Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal +2
In this short note, we initiate the study of the Linear Isomorphism Testing Problem in the setting of communication complexity, a natural linear algebraic generalization of the cla…
Testing Isomorphism of Boolean Functions over Finite Abelian Groups
Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal +2
Let and be Boolean functions over a finite Abelian group , where is fully known, and we have {\em query access} to , that is, given any $x \in \mathcal{…
About almost covering subsets of the hypercube
Arijit Ghosh, Chandrima Kayal, Soumi Nandi
Let be a field, and consider the hypercube in . Sziklai and Weiner (Journal of Combinatorial Theory, Series A 2022) showed that if a p…
Approximate Degree Composition for Recursive Functions
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal +2
Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have conc…
Relations between monotone complexity measures based on decision tree complexity
Farzan Byramji, Vatsal Jha, Chandrima Kayal +1
In a recent result, Knop, Lovett, McGuire and Yuan (STOC 2021) proved the log-rank conjecture for communication complexity, up to log n factor, for any Boolean function composed wi…