Towards Better Separation between Deterministic and Randomized Query Complexity

Sagnik Mukhopadhyay, Swagato Sanyal

We show that there exists a Boolean function $F$ which observes the following separations among deterministic query complexity $(D(F))$, randomized zero error query complexity $(R_…