Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-181 | 20th November 2023 23:59

Hardness Condensation by Restriction


Authors: Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
Publication: 21st November 2023 04:43
Downloads: 309


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.

ISSN 1433-8092 | Imprint