Q The Query Complexity Zoo

Lifting: query complexity as a source of communication lower bounds

Why query-complexity measures are studied so intensely: composed with a small gadget, they transfer to communication complexity.

A lifting theorem says: for a suitable two-party gadget $g$ on $O(\log n)$ bits, $$\mathrm{M}^{\mathrm{cc}}(f\circ g^n) \;=\; \Theta\big(\mathrm{M}(f)\cdot \log n\big)$$ for the appropriate pair of query and communication measures $\mathrm{M}$. Known for deterministic [GPW18], randomized, and several LP-based measures.

Consequences visible in this zoo:

  • The $\mathrm{D}$-vs-$\mathrm{SP}$ separation [GPW18] was found in order to refute the log-approximate-rank / partition-number conjecture in communication complexity.
  • [BenDavidKothari18] note that a zero-error lifting theorem would imply a bounded-error one, via sabotage complexity.
  • The strong direct sum of [BlaisBrody19] lifts to $\mathrm{R}^{\mathrm{cc}}(f^k)=\Theta(k\log k\cdot \mathrm{R}^{\mathrm{cc}}(f))$.
  • The $\mathrm{D}^{\oplus}$-vs-Fourier-sparsity question is the query analogue of the log-rank conjecture; see Parity decision trees vs Fourier sparsity (query log-rank).