ECCC-Report TR23-099https://eccc.weizmann.ac.il/report/2023/099Comments and Revisions published for TR23-099en-usMon, 10 Jul 2023 08:49:13 +0300
Revision 1
| On the Composition of Randomized Query Complexity and Approximate Degree |
Sourav Chakraborty,
Chandrima Kayal,
Rajat Mittal,
Manaswi Paraashar,
Swagato Sanyal,
Nitin Saurabh
https://eccc.weizmann.ac.il/report/2023/099#revision1For 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 well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering them satisfactorily.
It is known that the measures compose if one assumes various properties of the outer function $f$ (or inner function $g$). This paper extends the class of outer functions for which $\text{R}$ and $\widetilde{\text{deg}}$ compose.
A recent landmark result (Ben-David and Blais, 2020) showed that $\text{R}(f \circ g) = \Omega(\text{noisyR}(f)\cdot \text{R}(g))$. This implies that composition holds whenever $\text{noisyR}(f) = \tilde{\Theta}(\text{R}(f))$. We show two results:
[1.] When $\text{R}(f) = \Theta(n)$, then $\text{noisyR}(f) = \Theta(\text{R}(f))$. In other words, composition holds whenever the randomized query complexity of the outer function is full.
[2.] If $\text{R}$ composes with respect to an outer function, then $\text{noisyR}$ also composes with respect to the same outer function.
On the other hand, no result of the type $\widetilde{\text{deg}}(f \circ g) = \Omega(M(f) \cdot \widetilde{\text{deg}}(g))$ (for some non-trivial complexity measure $M(\cdot)$) was known to the best of our knowledge.
We prove that
\[
\widetilde{\text{deg}}(f\circ g) = \widetilde{\Omega}(\sqrt{\text{bs}(f)} \cdot \widetilde{\text{deg}}(g)),
\]
where $\text{bs}(f)$ is the block sensitivity of $f$.
This implies that $\widetilde{\text{deg}}$ composes when $\widetilde{\text{deg}}(f)$ is asymptotically equal to
$\sqrt{\text{bs}(f)}$.
It is already known that both $\text{R}$ and $\widetilde{\text{deg}}$ compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.Mon, 10 Jul 2023 08:49:13 +0300https://eccc.weizmann.ac.il/report/2023/099#revision1
Paper TR23-099
| On the Composition of Randomized Query Complexity and Approximate Degree |
Sourav Chakraborty,
Chandrima Kayal,
Manaswi Paraashar,
Rajat Mittal,
Swagato Sanyal,
Nitin Saurabh
https://eccc.weizmann.ac.il/report/2023/099For 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 well-studied problems in the field of analysis of Boolean functions, and yet we are far from answering them satisfactorily.
It is known that the measures compose if one assumes various properties of the outer function $f$ (or inner function $g$). This paper extends the class of outer functions for which $\text{R}$ and $\widetilde{\text{deg}}$ compose.
A recent landmark result (Ben-David and Blais, 2020) showed that $\text{R}(f \circ g) = \Omega(\text{noisyR}(f)\cdot \text{R}(g))$. This implies that composition holds whenever $\text{noisyR}(f) = \tilde{\Theta}(\text{R}(f))$. We show two results:
[1.] When $\text{R}(f) = \Theta(n)$, then $\text{noisyR}(f) = \Theta(\text{R}(f))$. In other words, composition holds whenever the randomized query complexity of the outer function is full.
[2.] If $\text{R}$ composes with respect to an outer function, then $\text{noisyR}$ also composes with respect to the same outer function.
On the other hand, no result of the type $\widetilde{\text{deg}}(f \circ g) = \Omega(M(f) \cdot \widetilde{\text{deg}}(g))$ (for some non-trivial complexity measure $M(\cdot)$) was known to the best of our knowledge.
We prove that
\[
\widetilde{\text{deg}}(f\circ g) = \widetilde{\Omega}(\sqrt{\text{bs}(f)} \cdot \widetilde{\text{deg}}(g)),
\]
where $\text{bs}(f)$ is the block sensitivity of $f$.
This implies that $\widetilde{\text{deg}}$ composes when $\widetilde{\text{deg}}(f)$ is asymptotically equal to
$\sqrt{\text{bs}(f)}$.
It is already known that both $\text{R}$ and $\widetilde{\text{deg}}$ compose when the outer function is symmetric. We also extend these results to weaker notions of symmetry with respect to the outer function.Sat, 08 Jul 2023 10:00:08 +0300https://eccc.weizmann.ac.il/report/2023/099