Query-to-Communication lifting using low-discrepancy gadgets

Sajin Koroth
Lifting theorems are theorems that relate the query complexity of a function f : {0, 1}^n â {0, 1} to the communication complexity of the composed function f â ¦ g^n, for some â gadgetâ g : {0, 1}^b à {0, 1}^b â {0, 1}. Such theorems allow transferring lower bounds from query complexity to the communication complexity, and have seen numerous applications in the recent years. In addition, such theorems can be viewed as...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.