Rectangles are Nonnegative Juntas

We develop a general method to transform query lower bounds for a boolean function f into communication lower bound for a composed function f o g^n where g: X x Y -> {0,1} is a small two-party “gadget”. Our main structure theorem states that each rectangle in the communication matrix of the composed function can be simulated by a nonnegative combination of juntas. This is the strongest yet formalization for the intuition that each low-communication randomized protocol can only “query” few inputs of f as encoded by the gadget g.

Consequently, we characterize the complexity of the composed function in all known one-sided zero-communication models (capturing NP, co-NP, lower-bound measures such as corruption, smooth rectangle bound, relaxed partition bound etc.) by a corresponding query complexity measure of f. As applications, we resolve several open problems from prior work.

Joint work with Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman.