Source Themes

We generalize the deterministic simulation theorem of Raz-Mckenzie, to any gadget which satisfies a certain hitting property. We prove that Inner-product and gap-Hamming satisfy this property, and, as a corollary, we obtain deterministic simulation theorem for these gadgets, where the gadget's input-size is logarithmic in the input-size of the outer function. This yields the first deterministic simulation theorem with a logarithmic gadget size, answering an open question posed by Goos-Pitassi-Watson.

Saks and Wigderson [FOCS 1986] conjectured that $R_0(f)=\mathrm{\Omega }(D(f{)}^{0.753\dots })$ for all Boolean functions $f$. We show that for the pointer function $GP{W}_{r\times s}$ defined by Goos, Pitassi, and Watson [FOCS 2015], the following hold: $R_1(GP{W}_{r\times s})=\tilde{\mathrm{\Theta }}(r+s)$ and $R_1(\overline{GP{W}_{r\times s}})=\tilde{\mathrm{\Theta }}(r+\sqrt{r}s)$, where $R_1$ denotes the randomized one-sided error query complexity. These results imply that (i) $R_0(GP{W}_{s^2\times s})=O(D(GP{W}_{s^2\times s}{)}^{2/3})$, thereby refuting the conjecture of Saks and Wigderson, and (ii) $R_1(GP{W}_{s\times s})=\tilde{O}(R_0(GP{W}_{s\times s}{)}^{2/3})$, thereby providing a polynomial separation between the randomized zero-error and one sided error query complexity measures.