Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-181 | 29th April 2024 21:59

Hardness Condensation by Restriction

RSS-Feed




Revision #1
Authors: Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
Accepted on: 29th April 2024 21:59
Downloads: 169
Keywords: 


Abstract:

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.



Changes to previous version:

Conference version


Paper:

TR23-181 | 20th November 2023 23:59

Hardness Condensation by Restriction





TR23-181
Authors: Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov
Publication: 21st November 2023 04:43
Downloads: 600
Keywords: 


Abstract:

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