For two Boolean functions f and g acting on n and m bits respectively, their composition f o g is a Boolean function on nm bits defined as follows. Its input is thought of as consisting of n blocks, each m bits long. f o g is computed first by computing g on each block, and then by computing f on the n resulting bits.
This talk is about one-way communication complexity of composed functions. Here, there are two communicating parties, and the input bits are distributed between them. One party sends a message to the other, based on which the other party outputs their guess of the value of the function on the jointly held input.
Suppose there is an algorithm for f that queries few bits of f, possibly randomly, and outputs the value of f. Suppose further that g is a function on very few bits. Then, the two communicating parties can simulate this algorithm and compute the composed function by communicating about as many bits as the algorithm queries.
The question we ask is if there is a communication protocol that is significantly cheaper than this naive protocol. We address this question for two choices of g: the AND function and the Inner-Product function.
This talk is based on joint work with Nikhil Mande and Suhail Sherif.
Link to the pre-print: https://arxiv.org/pdf/2105.01963.pdf
