Rectangles are Nonnegative Juntas
Thursday, March 19, 2015 - 2:00pm - 2:40pm
Klaus 1116
Raghu Meka (University of California, Los Angeles)
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.
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.