Sagnik Mukhopadhyay
Sagnik Mukhopadhyay
Home
Experience
Publications
Contact
Light
Dark
Automatic
Deterministic
Towards Better Separation between Deterministic and Randomized Query Complexity
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_0(F))$ and randomized one-sided error query complexity $(R_1(F))$: $R_1(F) = \widetilde{O}(\sqrt{D(F)})$ and $R_0(F)=\widetilde{O}(D(F))^{3/4}$.
Sagnik Mukhopadhyay
,
Swagato Sanyal
PDF
Cite
Slides
DOI
arXiv
Cite
×