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 ( k 3/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.

Authors

• Mika Göös
• Ilan Newman
• Artur Riazanov
• Dmitry Sokolov 0001

Keywords

• communication complexity
• hardness condensation
• query complexity