ECCC-Report TR23-181https://eccc.weizmann.ac.il/report/2023/181Comments and Revisions published for TR23-181en-usMon, 29 Apr 2024 21:59:26 +0300
Revision 1
| Hardness Condensation by Restriction |
Mika Göös,
Ilan Newman,
Artur Riazanov,
Dmitry Sokolov
https://eccc.weizmann.ac.il/report/2023/181#revision1Can 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.Mon, 29 Apr 2024 21:59:26 +0300https://eccc.weizmann.ac.il/report/2023/181#revision1
Paper TR23-181
| Hardness Condensation by Restriction |
Mika Göös,
Ilan Newman,
Artur Riazanov,
Dmitry Sokolov
https://eccc.weizmann.ac.il/report/2023/181Can 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.Tue, 21 Nov 2023 04:43:51 +0200https://eccc.weizmann.ac.il/report/2023/181