Raz-McKenzie simulation with the inner product gadget

In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions f composed with the Inner Product gadget 1ip(x, y) = P i xiyi mod 2 of logarithmic size. In other words, given a function f : {0, 1} n → {0, 1} with deterministic query complexity D(f), we show that the deterministic communication complexity of the composed function f ◦ 1 n ip is Θ(D(f) log n), where f ◦ 1 n ip(x, y) = f(1ip(x 1 , y 1 ), . . . , 1ip(x n , y n )) where x = (x 1 , . . . , x n ), y = (y 1 , . . . , y n ) and each x i and y i are O(log n) bit strings. In [RM97] and [GPW15], the simulation algorithm is implemented for functions composed with the Indexing gadget, where the size of the gadget is polynomial in the input length of the outer function f.