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

Paul Beame, Sajin Koroth

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 com…