All reports by Author Chandrima Kayal:

__
TR23-099
| 8th July 2023
__

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh#### On the Composition of Randomized Query Complexity and Approximate Degree

Revisions: 1

__
TR23-044
| 28th March 2023
__

Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar#### Separations between Combinatorial Measures for Transitive Functions

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh

For any Boolean functions $f$ and $g$, the question whether $\text{R}(f\circ g) = \tilde{\Theta}(\text{R}(f) \cdot \text{R}(g))$, is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether $\widetilde{\text{deg}}(f\circ g) = \tilde{\Theta}(\widetilde{\text{deg}}(f)\cdot\widetilde{\text{deg}}(g))$. These questions are two of the most important and ... more >>>

Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar

The role of symmetry in Boolean functions $f:\{0,1\}^n \to \{0,1\}$ has been extensively studied in complexity theory.

For example, symmetric functions, that is, functions that are invariant under the action of $S_n$ is an important class of functions in the study of Boolean functions.

A function $f:\{0,1\}^n \to \{0,1\}$ ...
more >>>