22 June 2016, Theoretical Computer Science Seminar, Bruno Loff

We study the communication complexity of function composition: If we have an boolean function G: {0,1}^{2n} → {0,1}, called the *gadget* or the *inner function*, and a function F: {0,1}^p → R, called the *outer function*, what is the communication complexity of F ∘ G = F(G(x_1,y_1),...,G(x_p,y_p))?
Raz and McKenzie have shown that, when the inner function G is the indexing function, and p < n^Ω(1), then
CC(F ∘ G) = Q(F) log n
where CC is the deterministic communication complexity and Q is the deterministic query complexity.
We will show that if G is the inner-product mod 2, and p < 2^{n/20}, then up to multiplicative constants:
CC(F ∘ G) = Q(F) n
We also report some progress in showing the randomized version of the same theorem.
This is joint work with Arkadev Chattopadhyay, Michal Koucky, and Sagnik Mukhopadhyay.