13 papers
Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
Chandrima Kayal, Sayantan Sen, Dániel Szabó
In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexit…
Certification complexity of Boolean functions
Chandrima Kayal, Sophie Laplante, Émile Larroque +2
Certificate complexity is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the va…
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…
Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal +2
Given Boolean functions \( f, g : \mathbb{F}_2^n \to \{-1,+1\} \), we say they are {\em linearly isomorphic} if there exists \( A \in \mathrm{GL}_n(\mathbb{F}_2) \) such that \( f(…
On higher multiplicity hyperplane and polynomial covers for symmetry preserving subsets of the hypercube
Arijit Ghosh, Chandrima Kayal, Soumi Nandi +1
Alon and Füredi (European J. Combin. 1993) gave a tight bound for the following hyperplane covering problem: find the minimum number of hyperplanes required to cover all points of…
On the Composition of Randomized Query Complexity and Approximate Degree
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal +3
For any Boolean functions and , the question whether , is known as the composition question for the randomized query complexity. Similarly,…
Almost covering all the layers of hypercube with multiplicities
Arijit Ghosh, Chandrima Kayal, Soumi Nandi
Given a hypercube in and , the -th layer of denotes the set of a…
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…