Can every $n$-bit boolean function with deterministic query complexity $k\ll n$ be restricted to $O(k)$ variables such that the query complexity remains $\Omega(k)$? That is, can query complexity be condensed via restriction? We study such hardness condensation questions in both query and communication complexity, proving two main results.

$\bullet~$ $\mathbf{Negative}$: ... more >>>