Note that \(\mathsf {Q}(\mbox{Promise-}\mathsf {OR})\)  is \(\Theta (\sqrt{n})\)  [1]}, [2]}. Thus, \(\mbox{Promise-}\mathsf {OR}\)  shows that there exist a function for which \(\mathsf {CG}^*(f) = \omega (\mathsf {Q}(f))\)  (as opposed to the randomized model where \(\mathsf {CG}^{\text{pub}}(f) \le O(\mathsf {R}(f))\) . On the other hand,
