Query-to-Communication Lifting for BPP

Introduction

A query-to-communication lifting theorem (a.k.a. communication-to-query simulation theorem) translates lower bounds on some type of query complexity (a.k.a. decision tree complexity) [Ver99, BdW02, Juk12] of a boolean function $f$ into lower bounds on a corresponding type of communication complexity [KN97, Juk12, RY17] of a two-party version of $f$. See Table 1 for a list of several known results in this vein. In this work, we show a lifting theorem for bounded-error randomized (i.e., BPP-type) query/communication complexity. Such a theorem had been conjectured by [ABB+16b, BK16, CKLM17, WYY17] and (ad nauseam) by the current authors.

For a function $f\colon\{0,1\}^{n}\to\{0,1\}$ (called the outer function) and a two-party function $g\colon\mathcal{X}\times\mathcal{Y}\to\{0,1\}$ (called the gadget), their composition $f\circ g^{n}\colon\mathcal{X}^{n}\times\mathcal{Y}^{n}\to\{0,1\}$ is defined by

Here, Alice holds $x\in\mathcal{X}^{n}$ and Bob holds $y\in\mathcal{Y}^{n}$. Our result is proved for the popular index gadget ${\textsc{Ind}}_{m}\colon[m]\times\{0,1\}^{m}\to\{0,1\}$ mapping $(x,y)\mapsto y_{x}$. We use ${\text{BPP}}^{{\text{dt}}}$ and ${\text{BPP}}^{{\text{cc}}}$ to denote the usual bounded-error randomized query and communication complexities. That is, ${\text{BPP}}^{{\text{dt}}}(f)$ is the minimum cost of a randomized decision tree (distribution over deterministic decision trees) which, on each input $z$, outputs $f(z)$ with probability at least $2/3$, where the cost is the maximum number of queries over all inputs and outcomes of the randomness; ${\text{BPP}}^{{\text{cc}}}(F)$ is defined similarly but with communication protocols instead of decision trees.

Let $m=m(n)\coloneqq n^{256}$. For every $f\colon\{0,1\}^{n}\to\{0,1\}$,

2 What does it mean?

The upshot of our lifting theorem is that it automates the task of proving randomized communication lower bounds: we only need to show a problem-specific query lower bound for $f$ (which is often relatively simple), and then invoke the general-purpose lifting theorem to completely characterize the randomized communication complexity of $f\circ{\textsc{Ind}}_{m}^{n}$.

The lifting theorem is especially useful for constructing examples of two-party functions that have large randomized communication complexity, but low complexity in some other communication model. For example, one of the main results of Anshu et al. [ABB+16b] is a nearly $2.5$-th power separation between randomized and quantum (${\text{BQP}}^{{\text{cc}}}$) communication complexities for a total function $F$:

Previously, a quadratic separation was known (witnessed by set-disjointness). The construction of $F$ (and its ad hoc analysis) in [ABB+16b] was closely modeled after an analogous query complexity separation, ${\text{BPP}}^{{\text{dt}}}(f)\geq{\text{BQP}}^{{\text{dt}}}(f)^{2.5-o(1)}$, shown earlier by [ABK16]. Our lifting theorem can reproduce the separation (1) by simply taking $F\coloneqq f\circ{\textsc{Ind}}_{m}^{n}$ and using the query result of [ABK16] as a black-box. Here we only note that ${\text{BQP}}^{{\text{cc}}}(F)$ is at most a logarithmic factor larger than ${\text{BQP}}^{{\text{dt}}}(f)$, since a protocol can always efficiently simulate a decision tree.

In a similar fashion, we can unify (and in some cases simplify) several other existing results in communication complexity [Raz99, GJPW15, ABB+16b, BR17], including separations between ${\text{BPP}}^{{\text{cc}}}$ and the log of the partition number; see Section 5 for details. At the time of the writing, we are not aware of any new applications implied by our lifting theorem.

Gadget size.

A drawback with our lifting theorem is that it assumes gadget size $m=\operatorname{poly}(n)$, which limits its applicability. For example, we are not able to reproduce tight randomized lower bounds for important functions such as set-disjointness [KS92, Raz92, BJKS04] or gap-Hamming [CR12, She12, Vid13]. It remains an open problem to prove a lifting theorem for $m=O(1)$ even for the models studied in [GLM+16, KMR17].

Reformulation

Our lifting theorem holds for all $f$, even if $f$ is a partial function or a general relation (search problem). Thus the theorem is not really about the outer function at all; it is about the obfuscating ability of the index gadget ${\textsc{Ind}}_{m}$ to hide information about the input bits of $f$. To focus on what is essential, let us reformulate the lifting theorem in a more abstract way that makes no reference to $f$.

Write $G\coloneqq g^{n}$ for $g\coloneqq{\textsc{Ind}}_{m}$. We view $G$’s input domain $[m]^{n}\times(\{0,1\}^{m})^{n}$ as being partitioned into slices $G^{-1}(z)=\{(x,y):G(x,y)=z\}$, one for each $z\in\{0,1\}^{n}$; see (a) below. We will eventually consider randomized protocols, but suppose for simplicity that we are given a deterministic protocol $\Pi$ of communication cost $|\Pi|$. The most basic fact about $\Pi$ is that it induces a partition of the input domain into at most $2^{|\Pi|}$ rectangles (sets of the form $X\times Y$ where $X\subseteq[m]^{n}$, $Y\subseteq(\{0,1\}^{m})^{n}$); see (b) below. The rectangles are in 1-to-1 correspondence with the leaves of the protocol tree, which are in 1-to-1 correspondence with the protocol’s transcripts (root-to-leaf paths; each path is a concatenation of messages). Fixing some $z\in\{0,1\}^{n}$, we are interested in the distribution over transcripts that is generated when $\Pi$ is run on a uniform random input from the slice $G^{-1}(z)$; see (c) below.

[b(-1mm),l(-3mm),r(-3mm),t(-1mm)]slices(.42) \lbl[c]6,60;$[m]^{n}$ \lbl[c]70,110;$(\{0,1\}^{m})^{n}$ \lbl[c]70,7;(a) \lbl[c]190,7;(b) \lbl[c]310,7;(c)

2 The reformulation

We devise a randomized decision tree that on input $z$ outputs a random transcript distributed close (in total variation distance) to that generated by $\Pi$ on input $(\bm{x},\bm{y})\sim G^{-1}(z)$. (We always use boldface letters for random variables.)

Let $\Pi$ be a deterministic protocol with inputs from the domain of $G=g^{n}$. There is a randomized decision tree of cost $O(|\Pi|/\log n)$ that on input $z\in\{0,1\}^{n}$ samples a random transcript (or outputs $\bot$ for failure) such that the following two distributions are $o(1)$-close:

Moreover, the simulation has “one-sided error”: $\operatorname{supp}(\bm{t}_{z})\subseteq\operatorname{supp}(\bm{t}^{\prime}_{z})\cup\{\bot\}$ for every $z$.

The lifting theorem (Theorem 1) follows as a simple consequence of the above reformulation. For the easy direction (“$\leq$”), any randomized decision tree for $f$ making $c$ queries can be converted into a randomized protocol for $f\circ g^{n}$ communicating $c\cdot O(\log n)$ bits, where the $O(\log n)$ factor is the deterministic communication complexity of the gadget. For the nontrivial direction (“$\geq$”), suppose we have a randomized protocol $\bm{\Pi}$ (viewed as a probability distribution over deterministic protocols) that computes $f\circ g^{n}$ (with error $\leq 1/3$, say) and each $\Pi\sim\bm{\Pi}$ communicates at most $|\Pi|\leq c$ bits. We convert this into a randomized decision tree for $f$ of query cost $O(c/\log n)$ as follows.

Pick a deterministic $\Pi\sim\bm{\Pi}$ (using random coins of the decision tree).

Run the randomized decision tree for $\Pi$ from Theorem 2 that samples a transcript $t\sim\bm{t}_{z}(\Pi)$.

Output the value of the leaf reached in $t$.

The resulting decision tree has bounded error on input $z$:

3 Extensions

The correctness of our simulation hinged on the property of BPP-type algorithms that the mixture of correct output distributions is correct. In fact, the “moreover” part in Theorem 2 allows us to get a lifting theorem for one-sided error (RP-type) and zero-sided error (ZPP-type) query/communication complexity: if the randomized protocol $\bm{\Pi}$ on every input $(x,y)\in G^{-1}(z)$ outputs values in $\{f(z),\bot\}$, so does our decision tree simulation on input $z$. Funnily enough, it was previously known that the existence of a query-to-communication lifting theorem for ZPP (for index gadget) implies the existence of a lifting theorem for BPP in a black-box fashion [BK16]. We also mention that Theorem 2 in fact holds with $1/\!\operatorname{poly}(n)$-closeness (instead of $o(1)$) for an arbitrarily high degree polynomial, provided $m$ is chosen to be a correspondingly high enough degree polynomial in $n$.

Simulation

We now prove Theorem 2. Fix a deterministic protocol $\Pi$ henceforth. We start with a high-level sketch of the simulation, and then fill in the details.

The randomized decision tree will generate a random transcript of $\Pi$ by taking a random walk down the protocol tree of $\Pi$, guided by occasional queries to the bits of $z$. The design of our random walk is dictated by one (and only one) property of the slice sets $G^{-1}(z)$:

Uniform marginals lemma (informal): For every $z\in\{0,1\}^{n}$ and every rectangle $X\times Y$ where $X$ is “dense” and $Y$ is “large”, the uniform distribution on $G^{-1}(z)\cap X\times Y$ has both of its marginal distributions close to uniform on $X$ and $Y$, respectively.

This immediately suggests a way to begin the randomized simulation. Each node of $\Pi$’s protocol tree is associated with a rectangle $X\times Y$ of all inputs that reach that node. We start at the root where, initially, $X\times Y=[m]^{n}\times(\{0,1\}^{m})^{n}$. Suppose Alice communicates the first bit $b\in\{0,1\}$. This induces a partition $X=X^{0}\cup X^{1}$ where $X^{b}$ consists of those inputs where Alice sends $b$. When $\Pi$ is run on a random input $(\bm{x},\bm{y})\sim G^{-1}(z)$, the above lemma states that $\bm{x}$ is close to uniform on $X$ and hence the branch $X^{b}$ is taken with probability roughly $|X^{b}|/|X|$. Our idea for a simulation is this: we pretend that $\bm{x}\sim X$ is perfectly uniform so that our simulation takes the branch $X^{b}$ with probability exactly $|X^{b}|/|X|$. It follows that the first bit sent in the two scenarios ($\bm{t}_{z}$ and $\bm{t}^{\prime}_{z}$) is distributed close to each other. We can continue the simulation in the same manner, updating $X\leftarrow X^{b}$ (and similarly $Y\leftarrow Y^{b}$ when Bob speaks), as long as $X\times Y$ remains “$\text{dense}\times\text{large}$”.

A convenient property of the index gadget is that Bob’s $nm$-bit input is much longer than Alice’s $n\log m$-bit input. Consequently, the simulation will not need to go out of its way to maintain the “largeness” of Bob’s set $Y$—we will argue that it naturally remains “large” enough with high probability throughout the simulation.

Density.

The interesting case is when Alice’s set $X$ ceases to be “dense”. Our idea is to promptly restore “density” by computing a density-restoring partition $X=\bigcup_{i}X^{i}$ with the property that each $X^{i}$ is fixed on some subset of blocks $I_{i}\subseteq[n]$ (which “caused” a density violation), and such that $X^{i}$ is again “dense” on the remaining blocks $[n]\smallsetminus I_{i}$. Moreover, $|I_{i}|$ will typically be bounded in terms of the number of bits communicated so far.

After Alice has partitioned $X=\bigcup_{i}X^{i}$ we will follow the branch $X^{i}$ (updating $X\leftarrow X^{i}$) with probability $|X^{i}|/|X|$; this random choice is justified by the uniform marginals lemma, since it imitates what would happen on a uniform random input from $G^{-1}(z)$. Since we made Alice’s pointers $X^{i}_{I_{i}}$ fixed, say, to value $\alpha\in[m]^{I_{i}}$, we need to fix the corresponding pointed-to bits on Bob’s side so as to make the output of the gadgets $g^{n}(X^{i},Y)$ consistent with $z$ on the fixed coordinates. At this point, our decision tree queries all the bits $z_{I_{i}}\in\{0,1\}^{I_{i}}$ and we argue that we can indeed typically restrict Bob’s set to some still-“large” $Y^{i}\subseteq Y$ to ensure $g^{I_{i}}(X^{i}_{I_{i}}\times Y^{i}_{I_{i}})=\{z_{I_{i}}\}$. Now that we have recovered “density” on the unfixed blocks, we may continue the simulation as before (relativized to unfixed blocks).

2 Tools

Let us make the notions of “dense” and “large” precise. Let $\mathbf{H}_{\infty}(\bm{x})\coloneqq\min_{x}\log(1/\mathbf{Pr}[\bm{x}=x])$ denote the usual min-entropy of a random variable $\bm{x}$. Supposing $\bm{x}$ is distributed over a set $X$, we define the deficiency of $\bm{x}$ as the nonnegative quantity $\mathbf{D}_{\infty}(\bm{x})\coloneqq\log|X|-\mathbf{H}_{\infty}(\bm{x})$. A basic property, which we use freely and repeatedly throughout the proof, is that marginalizing $\bm{x}$ to some coordinates (assuming $X$ is a product set) cannot increase the deficiency. For a set $X$ we use the boldface $\bm{X}$ to denote a random variable uniformly distributed on $X$.

A random variable $\bm{x}\in[m]^{J}$ (where $J$ is some index set) is called $\delta$-dense if for every nonempty $I\subseteq J$, the blocks $\bm{x}_{I}$ have min-entropy rate at least $\delta$, that is, $\mathbf{H}_{\infty}(\bm{x}_{I})\geq\delta\cdot|I|\log m$. (Note that $\bm{x}_{I}$ is marginally distributed over $[m]^{I}$.)

Suppose $\bm{X}$ is $0.9$-dense and $\mathbf{D}_{\infty}(\bm{Y})\leq n^{3}$. Then for any $z\in\{0,1\}^{n}$, the uniform distribution on $G^{-1}(z)\cap X\times Y$ (which is nonempty) has both of its marginal distributions $1/n^{2}$-close to uniform on $X$ and $Y$, respectively.

We postpone the proof of the lemma to Section 4, and instead concentrate here on the simulation itself—its correctness will mostly rely on this lemma. Actually, we need a slightly more general-looking statement that we can easily apply when some blocks in $X$ have become fixed during the simulation. To this end, we introduce terminology for such rectangles $X\times Y$. Note that 4 below specializes to 3 by taking $\rho=*^{n}$.

For a partial assignment $\rho\in\{0,1,*\}^{n}$, define its free positions as $\operatorname{free}\rho\coloneqq\rho^{-1}(*)\subseteq[n]$, and its fixed positions as $\operatorname{fix}\rho\coloneqq[n]\smallsetminus\operatorname{free}\rho$. A rectangle $X\times Y$ is called $\rho$-structured if $\bm{X}_{\operatorname{free}\rho}$ is $0.9$-dense, $\bm{X}_{\operatorname{fix}\rho}$ is fixed, and each output in $G(X\times Y)$ is consistent with $\rho$.

Suppose $X\times Y$ is $\rho$-structured and $\mathbf{D}_{\infty}(\bm{Y})\leq n^{3}$. Then for any $z\in\{0,1\}^{n}$ consistent with $\rho$, the uniform distribution on $G^{-1}(z)\cap X\times Y$ (which is nonempty) has both of its marginal distributions $1/n^{2}$-close to uniform on $X$ and $Y$, respectively.

[c]190,-10;Illustration of $\bm{x}\sim X$ and $\bm{y}\sim Y$ where $X\times Y$ is $\rho$-structured for $\rho\coloneqq 10\!*\!*$

[c]38,150;$x_{1}$ \lbl[c]38,110;$x_{2}$ \lbl[c]38,70;$\bm{x}_{3}$ \lbl[c]38,30;$\bm{x}_{4}$

[l]325,148;$=\bm{y}_{1}$ \lbl[l]325,108;$=\bm{y}_{2}$ \lbl[l]325,68;$=\bm{y}_{3}$ \lbl[l]325,28;$=\bm{y}_{4}$

[c]130,150;$*$ \lbl[c]150,150;$*$ \lbl[c]170,150;$*$ \lbl[c]190,150;$*$ \lbl[c]210,150;$*$ \lbl[c]230,150;$*$ \lbl[c]250,150;$*$ \lbl[c]270,150;$*$ \lbl[c]310,150;$*$

[c]130,110;$*$ \lbl[c]150,110;$*$ \lbl[c]170,110;$*$ \lbl[c]190,110;$*$ \lbl[c]230,110;$*$ \lbl[c]250,110;$*$ \lbl[c]270,110;$*$ \lbl[c]290,110;$*$ \lbl[c]310,110;$*$

[c]130,70;$*$ \lbl[c]150,70;$*$ \lbl[c]170,70;$*$ \lbl[c]190,70;$*$ \lbl[c]210,70;$*$ \lbl[c]230,70;$*$ \lbl[c]250,70;$*$ \lbl[c]270,70;$*$ \lbl[c]290,70;$*$ \lbl[c]310,70;$*$

[c]130,30;$*$ \lbl[c]150,30;$*$ \lbl[c]170,30;$*$ \lbl[c]190,30;$*$ \lbl[c]210,30;$*$ \lbl[c]230,30;$*$ \lbl[c]250,30;$*$ \lbl[c]270,30;$*$ \lbl[c]290,30;$*$ \lbl[c]310,30;$*$

3 Density-restoring partition

Fix some set $X\subseteq[m]^{J}$. (In our application, $J\subseteq[n]$ will correspond to the set of free blocks during the simulation.) We describe a procedure that takes $X$ and outputs a density-restoring partition $X=\bigcup_{i}X^{i}$ such that each $\bm{X}^{i}$ is fixed on some subset of blocks $I_{i}\subseteq J$ and $0.9$-dense on $J\smallsetminus I_{i}$. The procedure associates a label of the form “$x_{I_{i}}=\alpha_{i}$” with each part $X_{i}$, recording which blocks we fixed and to what value. If $\bm{X}$ is already $0.9$-dense, the procedure outputs just one part: $X$ itself.

Let $I\subseteq J$ be a maximal subset (possibly $I=\emptyset$) such that $\bm{X}_{I}$ has min-entropy rate $<0.9$, and let $\alpha\in[m]^{I}$ be an outcome witnessing this: $\mathbf{Pr}[\bm{X}_{I}=\alpha]>m^{-0.9|I|}$.

Output part $X^{(x_{I}=\alpha)}\coloneqq\{x\in X:x_{I}=\alpha\}$ with label “$x_{I}=\alpha$”.

Update $X\leftarrow X\smallsetminus X^{(x_{I}=\alpha)}$.

$X^{1}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><msup><mi>X</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">X^{2}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8641em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.0785em;">X</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8641em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span></span></span>X^{3}$$X^{4}$“$x_{I_{1}}\!=\alpha_{1}$”“$x_{I_{2}}\!=\alpha_{2}$”“$x_{I_{3}}\!=\alpha_{3}$”“$x_{I_{4}}\!=\alpha_{4}$”\neq\alpha_{1}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo mathvariant="normal">≠</mo><msub><mi>α</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">\neq\alpha_{2}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em;"></span><span class="mrel"><span class="mrel"><span class="mord vbox"><span class="thinbox"><span class="rlap"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em;"></span><span class="inner"><span class="mord"><span class="mrel"></span></span></span><span class="fix"></span></span></span></span></span><span class="mspace nobreak"></span><span class="mrel">=</span></span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.0037em;">α</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:-0.0037em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span>\neq\alpha_{3}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo mathvariant="normal">≠</mo><msub><mi>α</mi><mn>4</mn></msub></mrow><annotation encoding="application/x-tex">\neq\alpha_{4}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em;"></span><span class="mrel"><span class="mrel"><span class="mord vbox"><span class="thinbox"><span class="rlap"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em;"></span><span class="inner"><span class="mord"><span class="mrel"></span></span></span><span class="fix"></span></span></span></span></span><span class="mspace nobreak"></span><span class="mrel">=</span></span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.0037em;">α</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:-0.0037em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">4</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span>=\alpha_{1}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>=</mo><msub><mi>α</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">=\alpha_{2}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.3669em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.0037em;">α</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:-0.0037em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></span>=\alpha_{3}$=\alpha_{4}$ We collect below the key properties of the partition $X=\bigcup_{i}X^{i}$ output by the procedure. Firstly, the partition indeed restores blockwise-density for the unfixed blocks. Secondly, the deficiency (relative to unfixed blocks) typically decreases proportional to the number of blocks we fixed.

Each $X^{i}$ (labeled “$x_{I_{i}}=\alpha_{i}$”) in the density-restoring partition satisfies the following.

$\bm{X}^{i}_{J\smallsetminus I_{i}}$ is $0.9$-dense

$\mathbf{D}_{\infty}(\bm{X}^{i}_{J\smallsetminus I_{i}})\leq\mathbf{D}_{\infty}(\bm{X})-0.1|I_{i}|\log m+\delta_{i}$ where $\delta_{i}\coloneqq\log(|X|/|\cup_{j\geq i}X^{j}|)$

Write $X^{\geqslant i}\coloneqq\bigcup_{j\geq i}X^{j}$ so that $\bm{X}^{i}=(\bm{X}^{\geqslant i}\mid\bm{X}^{\geqslant i}_{I_{i}}=\alpha_{i})$. Suppose for contradiction that some part $\bm{X}^{i}$ was not $0.9$-dense on $J\smallsetminus I_{i}$. Then there is some nonempty $K\subseteq J\smallsetminus I_{i}$ and an outcome $\beta\in[m]^{K}$ violating the min-entropy condition: $\mathbf{Pr}[\bm{X}^{i}_{K}=\beta]>m^{-0.9|K|}$. But this contradicts the maximality of $I_{i}$ since the larger set $I_{i}\cup K$ now violates the min-entropy condition for $\bm{X}^{\geqslant i}$:

This proves the first part. The second part is a straightforward calculation (intuitively, going from $X$ to $X^{\geqslant i}$ causes a $\delta_{i}$ increase in deficiency, going from $X^{\geqslant i}$ to $X^{i}$ causes a $\leq 0.9|I_{i}|\log m$ increase, and restricting from $J$ to $J\smallsetminus I_{i}$ causes a $|I_{i}|\log m$ decrease):

4 The simulation

To describe our simulation in a convenient language, we modify the deterministic protocol $\Pi$ into a refined deterministic protocol $\overline{\Pi}$; see Figure 1. Namely, we insert two new rounds of communication whose sole purpose is to restore density for Alice’s free blocks by fixing some other blocks and Bob’s corresponding bits. In short, we maintain the rectangle $X\times Y$ as $\rho$-structured for some $\rho$. Each communication round of $\Pi$ is thus replaced with a whole iteration in $\overline{\Pi}$. The new communication rounds do not affect the input/output behavior of the original protocol: any transcript of $\overline{\Pi}$ can be projected back to a transcript of $\Pi$ (by ignoring messages sent on lines 14, 16). One way to think about $\overline{\Pi}$ is that it induces a partition of the communication matrix that is a refinement of the one $\Pi$ induces. Therefore, for the purpose of proving Theorem 2, we can concentrate on simulating $\overline{\Pi}$ in place of $\Pi$. The randomized decision tree becomes simple to describe relative to $\overline{\Pi}$; see Figure 2.

Next, we proceed to show that our randomized decision tree is (1) correct: on input $z$ it samples a transcript distributed close to that of $\overline{\Pi}$ when run on $(\bm{x},\bm{y})\sim G^{-1}(z)$, and (2) efficient: the number of queries it makes is bounded in terms of $|\Pi|$ (the number of iterations in $\overline{\Pi}$).

5 Correctness: Transcript distribution

We show that for every $z\in\{0,1\}^{n}$ the following distributions are $o(1)$-close:

The following is the heart of the argument.

Consider a node $v$ at the beginning of an iteration in $\overline{\Pi}$’s protocol tree, such that $z$ is consistent with the associated $\rho$. Suppose $X\times Y$ is the $\rho$-structured rectangle at $v$, and assume that $\mathbf{D}_{\infty}(\bm{Y})\leq n^{3}$. Let $\bm{m}$ and $\bm{m}^{\prime}$ denote the messages sent in this iteration under $\bm{t}$ and $\bm{t}^{\prime}$ respectively (conditioned on reaching $v$). Then

$\bm{m}$ and $\bm{m}^{\prime}$ are $1/n^{2}$-close,

with probability at least $1-4/n^{2}$ over $\bm{m}$, at least a $2^{-(n\log m+2)}$ fraction of $Y$ is retained.

Before proving the lemma, let us use it to show that $\bm{t}$ and $\bm{t}^{\prime}$ are $o(1)$-close. For this, it suffices to exhibit a coupling such that $\mathbf{Pr}[\bm{t}=\bm{t}^{\prime}]\geq 1-o(1)$. Our coupling works as follows:

Begin at the root, and for each iteration of $\overline{\Pi}$:

Sample this iteration’s messages $\bm{m}$ and $\bm{m}^{\prime}$ according to an optimal coupling.

If $\bm{m}\neq\bm{m}^{\prime}$, or if $\bm{m}$ results in $<2^{-(n\log m+2)}$ fraction of $Y$ being retained (this includes the simulation’s failure case), then proceed to sample the rest of $\bm{t}$ and $\bm{t}^{\prime}$ independently.

It follows by induction on $k$ that after the $k$-th iteration, with probability at least $1-k\cdot 5/n^{2}$,

$\bm{t}$ and $\bm{t}^{\prime}$ match so far,

$\mathbf{D}_{\infty}(\bm{Y})\leq k\cdot(n\log m+2)\leq n^{3}$ where $Y$ is Bob’s set under $\bm{t}$ so far.

This trivially holds for $k=0$. For $k>0$, conditioned on (I) and (II) for iteration $k-1$, the assumptions of 6 are met and hence $\mathbf{Pr}[\bm{m}=\bm{m}^{\prime}]\geq 1-1/n^{2}$ and

By a union bound, with probability $\geq 1-5/n^{2}$, (I) and (II) continue to hold. Thus,

Since there are at most $n\log m$ iterations, we indeed always have $k\cdot(n\log m+2)\leq n^{3}$ (in (II)), and in the end we have $\mathbf{Pr}[\bm{t}=\bm{t}^{\prime}]\geq 1-(n\log m)\cdot 5/n^{2}\geq 1-o(1)$ and thus $\bm{t}$ and $\bm{t}^{\prime}$ are $o(1)$-close.

Let $\bm{x}\coloneqq\bm{X}$ be uniform over $X$, and $\bm{y}\coloneqq\bm{Y}$ be uniform over $Y$, and $(\bm{x}^{\prime},\bm{y}^{\prime})$ be uniform over $G^{-1}(z)\cap X\times Y$. By 4, $\bm{x}$ and $\bm{x}^{\prime}$ are $1/n^{2}$-close, and $\bm{y}$ and $\bm{y}^{\prime}$ are $1/n^{2}$-close.

First assume Bob sends a bit at $v$. Then $\bm{m}$ is some deterministic function of $\bm{y}$, and $\bm{m}^{\prime}$ is the same deterministic function of $\bm{y}^{\prime}$ (the bit sent on line 7); thus $\bm{m}$ and $\bm{m}^{\prime}$ are $1/n^{2}$-close since $\bm{y}$ and $\bm{y}^{\prime}$ are. Also, the second property in the lemma statement trivially holds.

Henceforth assume Alice sends a bit at $v$. Write $\bm{m}=\bm{b}\bm{i}\bm{s}$ (jointly distributed with $\bm{x}$) and $\bm{m}^{\prime}=\bm{b}^{\prime}\!\bm{i}^{\prime}\!\bm{s}^{\prime}$ (jointly distributed with $(\bm{x}^{\prime},\bm{y}^{\prime})$) as the concatenation of the three messages sent (on lines 11, 14, 16). Then $\bm{b}\bm{i}\bm{s}$ is some deterministic function of $\bm{x}$, and $\bm{b}^{\prime}\!\bm{i}^{\prime}\!\bm{s}^{\prime}$ is the same deterministic function of $\bm{x}^{\prime}$ ($\bm{s}$ and $\bm{s}^{\prime}$ depend on $z$, which is fixed); thus $\bm{m}$ and $\bm{m}^{\prime}$ are $1/n^{2}$-close since $\bm{x}$ and $\bm{x}^{\prime}$ are. A subtlety here is that there may be outcomes of $\bm{b}\bm{i}$ for which $\bm{s}$ is not defined (there is no corresponding child in $\overline{\Pi}$’s protocol tree, since Bob’s set would become empty), in which case our randomized decision tree fails and outputs $\bot$. But such outcomes have probability under $\bm{b}^{\prime}\!\bm{i}^{\prime}$, so it is still safe to say $\bm{m}$ and $\bm{m}^{\prime}$ are $1/n^{2}$-close, treating $\bm{s}$ as $\bot$ if it is undefined.

We turn to verifying the second property. Define $X^{bi}\times Y^{bi}\subseteq X\times Y$ as the rectangle at the end of the iteration if Alice sends $b$ and $i$, and note that $\bm{x}\in X^{\bm{b}\bm{i}}$ and $\bm{x}^{\prime}\in X^{\bm{b}^{\prime}\!\bm{i}^{\prime}}$. There is a coupling of $\bm{y}$ and $\bm{y}^{\prime}$ such that $\mathbf{Pr}[\bm{y}\neq\bm{y}^{\prime}]\leq 1/n^{2}$; we may imagine that $\bm{y}$ is jointly distributed with $(\bm{x}^{\prime},\bm{y}^{\prime})$: sample $(\bm{x}^{\prime},\bm{y}^{\prime})$ and then conditioned on the outcome of $\bm{y}^{\prime}$, sample $\bm{y}$ according to the coupling. Note that for each $bi$,

(since $\bm{x}^{\prime}\in X^{bi}$ implies $\bm{y}^{\prime}\in Y^{bi}$), and so

Since trivially $\mathbf{Pr}[\bm{x}\in X^{bi}]\geq 1/|X|\geq 2^{-n\log m}$, combining (2) and (3) we have

One more detail to iron out is the “moreover” part in the statement of Theorem 2. The simulation we described does not quite satisfy this condition, but this is simple to fix: instead of halting with failure only when $Y$ becomes empty, we actually halt with failure when $\mathbf{D}_{\infty}(\bm{Y})>n^{3}$. This does not affect the correctness or efficiency analysis at all, but it ensures that we only output a transcript if $X\times Y$ is $\rho$-structured and $\mathbf{D}_{\infty}(\bm{Y})\leq n^{3}$ at the end, which by 4 guarantees that the transcript’s rectangle intersects the slice $G^{-1}(z)$ and thus $\bm{t}\in\operatorname{supp}(\bm{t}^{\prime})$.

6 Efficiency: Number of queries

We show that our randomized decision tree makes $O(|\Pi|/\log n)$ queries with high probability. If we insist on a decision tree that always makes this many queries (to match the statement of Theorem 2), we may terminate the execution early (with output $\bot$) whenever we exceed the threshold. This would incur only a small additional loss in the closeness of transcript distributions.

The simulation makes $O(|\Pi|/\log n)$ queries with probability $\geq 1-\min(2^{-|\Pi|},1/n^{\Omega(1)})$.

During the simulation, we view the quantity $\mathbf{D}_{\infty}(\bm{X}_{\operatorname{free}\rho})\geq 0$ as a nonnegative potential function. Consider a single iteration where lines 11, 14, 16 modify the sets $X$ and $\operatorname{free}\rho$.

In line 11, we shrink $X=X^{0}\cup X^{1}$ down to $X^{\bm{b}}$ where $\mathbf{Pr}[\bm{b}=b]=|X^{b}|/|X|$. Hence the increase in the potential function is $\gamma_{\bm{b}}\coloneqq\log(|X|/|X^{\bm{b}}|)$.

In line 14 (after $X\leftarrow X^{b}$), we shrink $X=\bigcup_{i}X^{i}$ down to $X^{\bm{i}}$ where $\mathbf{Pr}[\bm{i}=i]=|X^{i}|/|X|$. Moreover, in line 16, $|\!\operatorname{free}\rho|$ decreases by the number of bits we query. 5 says that the potential changes by $\delta_{\bm{i}}-\Omega(\log n)\cdot\textbf{\#}(\text{queries in this iteration})$ where $\delta_{\bm{i}}\coloneqq\log(|X|/|\cup_{j\geq\bm{i}}X^{j}|)$.

We will see later that for any iteration, $\mathbf{E}[\gamma_{\bm{b}}],\mathbf{E}[\delta_{\bm{i}}]\leq O(1)$.

For $j=1,\ldots,|\Pi|$, letting $\bm{\gamma}_{j},\bm{\delta}_{j}$ be the random variables $\gamma_{\bm{b}},\delta_{\bm{i}}$ respectively in the $j$-th iteration (and letting $\bm{\gamma}_{j}=\bm{\delta}_{j}=0$ for outcomes in which Alice does not communicate in the $j$-th iteration), the potential function at the end of the simulation is $\sum_{j}(\bm{\gamma}_{j}+\bm{\delta}_{j})-\Omega(\log n)\cdot\textbf{\#}(\text{queries in total})\geq 0$ and hence

By Markov’s inequality, this already suffices to show that with probability $\geq 0.9$ (say), the simulation uses $O(|\Pi|/\log n)$ queries. To get a better concentration bound, we would like for the $\bm{\gamma}_{j},\bm{\delta}_{j}$ variables (over all $j$) to be mutually independent, which they unfortunately generally are not. However, there is a trick to overcome this: we will define mutually independent random variables $\bm{c}_{j},\bm{d}_{j}$ (for all $j$) and couple them with the $\bm{\gamma}_{j},\bm{\delta}_{j}$ variables in such a way that each $\bm{\gamma}_{j}\leq\bm{c}_{j}$ and $\bm{\delta}_{j}\leq\bm{d}_{j}$ with probability $1$, and show that $\sum_{j}(\bm{c}_{j}+\bm{d}_{j})$ is bounded with very high probability, which implies the same for $\sum_{j}(\bm{\gamma}_{j}+\bm{\delta}_{j})$. For each $j$, do the following.

Sample a uniform real $\bm{q}_{j}\in[0,1)$ and define $\bm{d}_{j}\coloneqq\log(1/(1-\bm{q}_{j}))$ and let $\bm{\delta}_{j}\coloneqq\delta_{\bm{i}}$ where $\bm{i}$ is such that $\bm{q}_{j}$ falls in the $\bm{i}$-th interval, assuming we have partitioned $[0,1)$ into half-open intervals with lengths $|X^{i}|/|X|$ in the natural left-to-right order (where $X,X^{1},X^{2},\ldots$ are the sets that arise in the second half of the $j$-th iteration, conditioned on the outcomes of the first half and previous iterations). Note that $\bm{\delta}_{j}$ is correctly distributed, and that $\bm{\delta}_{j}\leq\bm{d}_{j}$ with probability $1$ (specifically, if $\bm{i}=i$ then $\bm{\delta}_{j}=\log(|X|/|\cup_{j\geq i}X^{j}|)\leq\log(1/(1-\bm{q}_{j}))=\bm{d}_{j}$). Also note that, as claimed earlier, $\mathbf{E}[\bm{\delta}_{j}]\leq\mathbf{E}[\bm{d}_{j}]\leq\mathbf{E}[\bm{c}_{j}]\leq O(1)$. For future use, note that \mathbf{E}\bigl{[}2^{\bm{d}_{j}/2}\bigr{]}\leq\mathbf{E}\bigl{[}2^{\bm{c}_{j}/2}\bigr{]}\leq O(1).

Now for some sufficiently large constants $C,C^{\prime}$ we have

If $|\Pi|\leq o(\log n)$ then a similar calculation shows that \mathbf{Pr}\bigl{[}\textbf{\#}(\text{queries in total})\geq 1\bigr{]}\leq 1/n^{\Omega(1)}. ∎

Uniform Marginals Lemma

We prove a slightly stronger statement formulated in 8 below. For terminology, we say a distribution $\mathcal{D}_{1}$ is $\varepsilon$-pointwise-close to a distribution $\mathcal{D}_{2}$ if for every outcome, the probability under $\mathcal{D}_{1}$ is within a factor $1\pm\varepsilon$ of the probability under $\mathcal{D}_{2}$. As a minor technicality (for the purpose of deriving 4 from 8), we say that a random variable $\bm{x}\in[m]^{J}$ is $\delta$-essentially-dense if for every nonempty $I\subseteq J$, $\mathbf{H}_{\infty}(\bm{x}_{I})\geq\delta\cdot|I|\log m-1$ (the difference from 1 is the “$-1$”); we also define $\rho$-essentially-structured in the same way as $\rho$-structured but requiring $\bm{X}_{\operatorname{free}\rho}$ to be only $0.9$-essentially-dense instead of $0.9$-dense. The following strengthens a lemma from [GKPW17], which implied that $G(\bm{X},\bm{Y})$ has full support over the set of all $z$ consistent with $\rho$.

Suppose $X\times Y$ is $\rho$-essentially-structured and $\mathbf{D}_{\infty}(\bm{Y})\leq n^{3}+1$. Then $G(\bm{X},\bm{Y})$ is $1/n^{3}$-pointwise-close to the uniform distribution over the set of all $z$ consistent with $\rho$.

Let $(\bm{x},\bm{y})$ be uniformly distributed over $G^{-1}(z)\cap X\times Y$. We show that $\bm{x}$ is $1/n^{2}$-close to $\bm{X}$; a completely analogous argument works to show that $\bm{y}$ is $1/n^{2}$-close to $\bm{Y}$. Let $E\subseteq X$ be any test event. Replacing $E$ by $X\smallsetminus E$ if necessary, we may assume $|E|\geq|X|/2$. Since $X\times Y$ is $\rho$-structured, $E\times Y$ is $\rho$-essentially-structured. Hence we can apply 8 in both the rectangles $E\times Y$ and $X\times Y$:

A version of 8 (for the inner-product gadget) was proved in [GLM+16, §2.2] under the assumption that $\bm{X}$ and $\bm{Y}$ had low deficiencies: $\mathbf{D}_{\infty}(\bm{X}_{I}),\mathbf{D}_{\infty}(\bm{Y}_{I})\leq O(|I|\log n)$ for free blocks $I$. The key difference is that we only assume $\mathbf{D}_{\infty}(\bm{Y}_{I})\leq n^{3}+1$. We still follow the general plan from [GLM+16] but with a new step that allows us to reduce the deficiency of $\bm{Y}$.

The idea in [GLM+16] to prove that $\bm{z}\coloneqq G(\bm{X},\bm{Y})$ is pointwise-close to uniform is to study $\bm{z}$ in the Fourier domain, and show that $\bm{z}$’s Fourier coefficients (corresponding to free blocks) decay exponentially fast. That is, for every nonempty $I\subseteq\operatorname{free}\rho$ we want to show that the bias of $\oplus(\bm{z}_{I})$ (parity of the output bits $\bm{z}_{I}$) is exponentially small in $|I|$. Tools tailor-made for this situation exist: various “Xor lemmas” are known to hold for communication complexity (e.g., [Sha03]) that apply as long as $\bm{X}_{I}$ and $\bm{Y}_{I}$ have low deficiencies. All this is recalled in Section 4.2. This suggests that all that remains is to reduce our case of high deficiency (of $\bm{Y}_{I}$) to the case of low deficiency.

Reducing deficiency via buckets.

For the moment assume $I=[n]$ for simplicity of discussion. Our idea for reducing the deficiency of $\bm{Y}_{I}=\bm{Y}$ is as follows. We partition each $m$-bit string in $\bm{Y}\in(\{0,1\}^{m})^{n}$ into $m^{1/2}$ many buckets each of length $m^{1/2}$. We argue that $\bm{Y}$ can be expressed as a mixture of distributions $\bm{y}$, where $\bm{y}$ has few of its buckets fixed in each string $\bm{y}_{i}$, and for any way of choosing an unfixed bucket for each $\bm{y}_{i}$, the marginal distribution of $\bm{y}$ on the union $T$ of these buckets has deficiency as low as $\mathbf{D}_{\infty}(\bm{y}_{T})\leq 1$. Correspondingly, we argue that $\bm{X}$ may be expressed as a mixture of distributions $\bm{x}$ that have a nice form:

[b(3mm),t(1mm),r(7mm),l(-7mm)]bucket(.27) \lbl[c]38,110;$x_{1}$ \lbl[c]38,70;$\bm{x}_{2}$ \lbl[c]38,30;$\bm{x}_{3}$ \lbl[l]410,108;$=\bm{y}_{1}$ \lbl[l]410,68;$=\bm{y}_{2}$ \lbl[l]410,28;$=\bm{y}_{3}$

[c]365,110;fixed \lbl[c]365,70;fixed \lbl[c]365,30;fixed

[c]155,0;1st bucket \lbl[c]225,0;2nd bucket \lbl[c]295,0;3rd bucket \lbl[c]365,0;4th bucket

Here each pointer $\bm{x}_{i}$ ranges over a single bucket $T_{i}$. Moreover, for a large subset $I^{\prime}\subseteq[n]$ of coordinates, $T_{i}$ is unfixed in $\bm{y}_{i}$ for $i\in I^{\prime}$, and hence $\bm{y}$ has deficiency $\leq 1$ on the union of these unfixed buckets. The remaining few $i\in[n]\smallsetminus I^{\prime}$ are associated with fixed pointers $\bm{x}_{i}=x_{i}$ pointing into fixed buckets in $\bm{y}$. Consequently, we may interpret $(\bm{x},\bm{y})$ as a random input to ${\textsc{Ind}}_{m^{1/2}}^{n}$ by identifying each bucket $T_{i}$ with $[m^{1/2}]$. In this restricted domain, we can show that $(\oplus\circ g^{n})(\bm{x},\bm{y})$ is indeed very unbiased: the fixed coordinates do not contribute to the bias of the parity, and $(\bm{x}_{I^{\prime}},\bm{y}_{I^{\prime}})$ is a pair of low-deficiency variables for which an Xor lemma type calculation applies. The heart of the proof will be to find a decomposition of $\bm{X}\times\bm{Y}$ into such distributions $\bm{x}\times\bm{y}$.

In the remaining subsections, we carry out the formal proof of 8.

2 Fourier perspective

Henceforth we abbreviate $J\coloneqq\operatorname{free}\rho$. We employ the following calculation from [GLM+16], whose proof is reproduced in Section 4.6 for completeness. Here $\chi(z)\coloneqq(-1)^{\oplus(z)}$.

If a random variable $\bm{z}_{J}$ over $\{0,1\}^{J}$ satisfies \bigl{|}\mathbf{E}\bigl{[}\chi(\bm{z}_{I})\bigr{]}\bigr{|}\leq 2^{-5|I|\log n} for every nonempty $I\subseteq J$, then $\bm{z}_{J}$ is $1/n^{3}$-pointwise-close to uniform.

To prove 8, it suffices to take $\bm{z}_{J}=g^{J}(\bm{X}_{J},\bm{Y}_{J})$ above and show for every $\emptyset\neq I\subseteq J$,

$\mathbf{D}_{\infty}(\bm{X}_{I})\leq 0.1|I|\log m+1$,

$\mathbf{D}_{\infty}(\bm{Y}_{I})\leq n^{3}+1$.

As a warm-up, let us see how to obtain (4) by imagining that we are in the low-deficiency case, i.e., replacing assumption (ii) by

We present a calculation that is a very simple special case of, e.g., Shaltiel’s [Sha03] Xor lemma for discrepancy (relative to uniform distribution).

Let $M$ be the communication matrix of $g\coloneqq{\textsc{Ind}}_{m}$ but with $\{+1,-1\}$ instead of $\{0,1\}$ entries. The operator $2$-norm of $M$ is $\|M\|=2^{m/2}$ since the rows are orthogonal and each has $2$-norm $2^{m/2}$. The $|I|$-fold tensor product of $M$ then satisfies \bigl{\|}M^{\otimes|I|}\bigr{\|}=2^{|I|m/2} by the standard fact that the $2$-norm behaves multiplicatively under tensor product. Here $M^{\otimes|I|}$ is the communication matrix of the 2-party function $\chi\circ g^{I}$. We think of the distribution of $\bm{X}_{I}$ as an $m^{|I|}$-dimensional vector $\mathcal{D}_{\bm{X}_{I}}$, and of the distribution of $\bm{Y}_{I}$ as a $(2^{m})^{|I|}$-dimensional vector $\mathcal{D}_{\bm{Y}_{I}}$. Letting $\mathbf{H}_{2}$ ($\geq\mathbf{H}_{\infty}$) denote Rényi $2$-entropy, by (i) we have