Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth +2

Lifting theorems are theorems that relate the query complexity of a function $f:\{0,1{\}}^n\to \{0,1\}$ to the communication complexity of the composed function $f\circ g^n$, for…