Consider the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x; their goal is to cooperatively decide whether x belongs to L at small cost, where the cost measure is the number of bits of communication from the first player to the second player.

For any integer d>=3 and positive real epsilon we show that if satisfiability for n-variable d-CNF formulas has a protocol of cost O(n^{d-\epsilon}) then coNP is in NP/poly, which implies that the polynomial-time hierarchy collapses to the third level. The result even holds for conondeterministic protocols, and is tight as there exists a trivial deterministic protocol for epsilon = 0. Under the hypothesis that coNP is not in NP/poly, our result implies tight lower bounds for parameters of interest in several areas, including sparsification, probabilistically checkable proofs, instance compression, and kernelization in parameterized complexity.

Joint work with H. Dell.