



01278nas a2200133   4500008004100000245005800041210005700099260001500156520087600171100001501047700001701062700001601079856004901095       2017                        eng d00aRaz-McKenzie simulation with the inner product gadget0 aRazMcKenzie simulation with the inner product gadget  c2017/01/283 a<p>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 &rarr; {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.</p>1 aWu, Xiaodi1 aYao, Penghui1 aYuen, Henry  uhttps://eccc.weizmann.ac.il/report/2017/010/