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.
Arkadev Chattopadhyay,
Michal Koucký,
Bruno Loff,
Sagnik Mukhopadhyay