Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

22 June 2016, Theoretical Computer Science Seminar, Bruno Loff

Speaker: Bruno Loff (Prague)
Title: Some new results on the communication complexity of composition
Date: Wednesday 22 June 2016
Time: 15:00-16:00
Location: CWI room L017, Science Park 123, Amsterdam

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.

Please note that this newsitem has been archived, and may contain outdated information or links.