Hardness Condensation by Restriction
Can every n-bit boolean function with deterministic query complexity k≪ n be restricted to O(k) variables such that the query complexity remains ω(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. 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(k3/4). 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.
2-s2.0-85196645564
École Polytechnique Fédérale de Lausanne
University of Haifa
École Polytechnique Fédérale de Lausanne
École Polytechnique Fédérale de Lausanne
2024-06-10
9798400703836
2016
2027
REVIEWED
EPFL
Event name | Event acronym | Event place | Event date |
Vancouver, Canada | 2024-06-24 - 2024-06-28 | ||