Sagnik Mukhopadhyay: Simulation theorem and fork-lift

PRACTICALITIES

Lunch is served at 12:00 noon (register at  this doodle  at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for \(1\frac{1}{2}-2\) hours of more technical discussions.

ABSTRACT: Recently, proving theorems of the form that the communication complexity of a composed function \(f \circ g\) is essentially of the order of the decision tree complexity of f times the communication complexity of g has received a lot of attention. In particular, Goos-Pitassi-Watson (2015) simplified the proof of such a theorem for deterministic complexity due to Raz-McKenzie (1997) that worked only when g is the Indexing function. They used this theorem to settle a longstanding open problem in communication complexity. The Raz-McKenzie theorem needs the size of the Indexing gadget to be at least \(p^{20}\), where p is the number of instances of Index.

We identify a simple sufficient condition for g to be satisfied to prove such deterministic simulation theorems. Using this, we show that \(CC(f \circ IP) = \Omega(DT(f). n)\), provided \(n = \Omega(\log p)\), where IP is the inner-product function. This gives an exponential improvement over the gadget size of Raz-McKenzie.

We also prove a tight lower bound for randomized communication complexity of \(OrdSearch \circ IP\) in terms of randomized decision tree complexity of the function OrdSearch, which is \(\Omega(\log p)\). Proving a randomized simulation theorem remains elusive and we will discuss the hurdles that are needed to be faced and overcome.

This is a joint work with Arkadev Chattopadhyay (TIFR Mumbai), Michal Koucky and Bruno Loff (Charles University, Prague).