Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with res-parity proofs:
TR22-173 | 3rd December 2022
Paul Beame, Sajin Koroth

On Disperser/Lifting Properties of the Index and Inner-Product Functions

Revisions: 1

Query-to-communication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated `lifted' function obtained by composing the function with many copies of another function known as a gadget, have been instrumental in resolving many open questions in computational complexity. Several important complexity ... more >>>

ISSN 1433-8092 | Imprint