Almost quadratic gap between partition complexity and query/communication complexity

We show nearly quadratic separations between two pairs of complexity measures:

We show that there is a Boolean function $f$ with $D (f) = Ω ((D^{s c} (f))^{2 - o (1)})$ where $D (f)$ is the deterministic query complexity of $f$ and $D^{s c}$ is the subcube partition complexity of $f$ ;
As a consequence, we obtain that there is a communication task $f (x, y)$ such that $D^{c c} (f) = Ω (\log^{2 - o (1)} χ (f))$ where $D^{c c} (f)$ is the deterministic 2-party communication complexity of $f$ (in the standard 2-party model of communication) and $χ (f)$ is the partition number of $f$ . Both of those separations are nearly optimal: it is well known that $D (f) = O ((D^{s c} (f))^{2})$ and $D^{c c} (f) = O (\log^{2} χ (f))$ .

We show nearly quadratic separations between two pairs of complexity measures:

We show that there is a Boolean function $f$ with $D (f) = Ω ((D^{s c} (f))^{2 - o (1)})$ where $D (f)$ is the deterministic query complexity of $f$ and $D^{s c}$ is the subcube partition complexity of $f$ ;
As a consequence, we obtain that there is a communication task $f (x, y)$ such that $D^{c c} (f) = Ω (\log^{2 - o (1)} χ (f))$ where $D^{c c} (f)$ is the deterministic 2-party communication complexity of $f$ (in the standard 2-party model of communication) and $χ (f)$ is the partition number of $f$ . Both of those separations are nearly optimal: it is well known that $D (f) = O ((D^{s c} (f))^{2})$ and $D^{c c} (f) = O (\log^{2} χ (f))$ .

文献摘要