Author

Chandrima Kayal

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Oct 2026

Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model

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 complexity. In the classical setting, it is known that $\widetilde{\Theta}(\sqrt{N})$ queries are necessary and sufficient for both these testing pro...

Chandrima Kayal, Sayantan Sen, Dániel Szabó · 0 citations

Preprint Sep 2026

Certification complexity of Boolean functions

Certificate complexity $(C(f ))$ 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 value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is consta...

Chandrima Kayal, Sophie Laplante, É. Larroque et al. · 0 citations