Frage

I am trying to prove that the fooling set method does not give a good lower bound for the communication complexity of the inner product function. Specifically, I am trying to show that the best bound we get using the fooling set method is $$D(IP) \geq \Omega(\log n) $$

$D(IP)$ is the deterministic communication complexity of the inner product function. This implies that any fooling set for the inner product cannot have more than $n^2$ elements. How do I show this? I can verify the statement for specific instances, but I have no intuition for the proof.

Keine korrekte Lösung

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top