Description

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.

 

 

 

All scheduled dates:

Upcoming

No Upcoming activities yet

Past