Simulation Theorems via Pseudo-random Properties

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.

Our result also implies the previous results for the Indexing gadget, with better parameters than was previously known. Moreover, a simulation theorem with logarithmic-sized gadget implies a quadratic separation in deterministic communication complexity and logarithm of the $1$-partition number, no matter how high the $1$-partition number is with respect to the input size—something which is not achievable by previous results of Goos-Pitassi-Watson.