Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses

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 \geq 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, kernelization in parameterized complexity,
lossy compression, and probabilistically checkable proofs.

By reduction, the above statement holds for the vertex-cover problem
on $n$-vertex $d$-uniform hypergraphs for any integer $d \geq 2$.

This is joint work with Dieter van Melkebeek.