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}$: Query complexity cannot be condensed in general: There is a function $f$ with query complexity $k$ such that any restriction of $f$ to $O(k)$ variables has query complexity $O(k^{3/4})$.

$\bullet~$ $\mathbf{Positive}$: Randomised communication complexity can be condensed for the sink-of-xor function. This yields a quantitatively improved counterexample to the log-approximate-rank conjecture, achieving parameters conjectured by Chattopadhyay, Garg, and Sherif (2021).

Along the way we show the existence of Shearer extractors---a new type of seeded extractor whose output bits satisfy prescribed dependencies across distinct seeds.

Conference version

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}$: Query complexity cannot be condensed in general: There is a function $f$ with query complexity $k$ such that any restriction of $f$ to $O(k)$ variables has query complexity $O(k^{3/4})$.

$\bullet~$ $\mathbf{Positive}$: Randomised communication complexity can be condensed for the sink-of-xor function. This yields a quantitatively improved counterexample to the log-approximate-rank conjecture, achieving parameters conjectured by Chattopadhyay, Garg, and Sherif (2021).

Along the way we show the existence of Shearer extractors---a new type of seeded extractor whose output bits satisfy prescribed dependencies across distinct seeds.