Query-To-Communication Lifting Theorems

Abstract

Given a two-party gadget function g : X × Y → {0, 1} and an outer lifting function f : {0, 1} n → {0, 1}, we can define F = f◦g n : X n×Yn → {0, 1} that treats the input (x, y) = ((x1, . . . , xn),(y1, . . . , yn)) as n ‘blocks’and outputs F(x, y) = f(g(x1, y1),(x2, y2), . . . ,(xn, yn)). Using theorems of G¨o¨os, Kamath, Pitassi and Watson, I set out to explore the conditions on f, g and n, in various computational settings, that make it possible to decompose the complexity of F in terms of the complexity of f and g. These results lead directly to various bounds and counter-examples all across the complexity zoo.