1 概述

在字RAW模型中讨论Van Emde Boas树，y-fast树和融合树作为求一个元素的前序和后续的上界：

/[O(min/{lg/omega, lg_/omega n/})
/]

现在我们讨论前序问题cell-probe复杂性下界，特别的如果这个界是针对静态问题的并且将问题限定在多项式空间，我们在使用round elimination technique技术的communication model中得到下界为：

/[/Omega(min/{/frac{lg(/omega)}{lglg(n)},lg_/omega n/})
/]

上述下界表明通过求Van Emde Boas树和融合树的最小值可以得到求元素前序问题的最优的复杂度，可以达到/(lglg/)级。
上述得到的界是十分优雅的，它们只依赖于信息论（此处有一个问题：是否任何操作都可以做到这一点？）。上述上界都使用了位操作和C风格的操作，由此可以看出他们都依赖于一些计算机技术特性。

2 前人关于前序问题下界的研究

2.1问题描述

给定一个数据结构（由n个/(/omega/)-bits整数组成的集合S）和一个查询操作（查找元素x， 并且x可能不在S中），我们的目标是尽可能快的找到集合S中x的前序元素。我们可以用/(O(2^/omega)/)的空间存储预先计算好的所有结果，实现恒定时间的查询。为了避免将问题平凡化，我们假设数据结构用/(O(n^(O(1)))/)的空间。
我们即将讨论的结果实际上是针对一个更容易的问题，即染色前序问题。在此问题中，S的每个元素都被染成红色或蓝色，目标是返回S中x的前序的颜色。由于我们可以用前身问题的解决方案来解决彩色前身问题，这就为我们的原始问题提供了一个更强的下限。

2.2结果

• Ajtai证明了第一个/(/omega(1)/)（即超常数）下界，表明/(/forall/omega/)，/(/exists n/)可以得到/(/Omega(/sqrt/lg/omega)/)查询时间。
• Miltersen在communication复杂度方面更连贯地重新表述了相同的证明思想。然后展示了两个结果：
  • /(/forall/omega/)，/(/exists n/)可以得到/(/Omega(/sqrt/lg/omega)/)查询时间
  • /(/forall n/)，/(/exists/omega/)可以得到/(/Omega(/sqrt/lg n)/)查询时间
• Miltersen, Nisan, Safra, 和Widgerson 介绍了round elimination technique ，并利用它给出了相同下限的简洁证明。
• Beame和Fich证明了两个强界。
  • /(/forall/omega/)，/(/exists n/)可以得到/(/Omega(/frac{/lg/omega}{/lg/lg/omega})/)查询时间
  • /(/forall n/)，/(/exists/omega/)可以得到/(/Omega(/sqrt/frac{/lg n}{/lg/lg n})/)查询时间

他们还给出了一个静态数据结构取得/(O(min/{/frac{/lg/omega}{/lg/lg/omega},/sqrt/frac{/lg n}{/lg/lg n}/})/)，该方法表明，如果我们坚持使用纯界（仅依赖于n或仅依赖于w的界），上述两个强界是最佳的。

• Xiao独立地证明了与Beame和Fich相同的两个下界。
• Sen和Venkatesh给出了一个更强的round elimination定理的版本。它给出了Beame和Fich以及Xiao的相同界的一个更简洁的证明。Fich和Xiao的相同界提供了更简洁的证明。
• Patrascu和Thorup给出了静态问题中n、w和空间之间的严格权衡。假设空间为/(n·2^a/) 其中/(a=O(/lg/lg n)/)，他们发现了一个下限为:

/[/Theta(min/{/log_/omega n, /lg(/frac{/omega – /lg n}{a}),/frac{/lg/frac{/omega}{a}}{/lg(/frac{a}{/lg n}/lg/frac{w}{a})},/frac{/lg/frac{/omega}{a}}{/lg(/lg/frac{/omega}{a}//lg/frac{/lg n}{a})}/})
/]

一些直观性理解：
– 第一个项看起来像融合树。
– 第二项约等于是/(/lg w/)，相似于Van Emde Boas。
– 最后两个项没有一个好的直观性理解。它们看起来有点类似于Van Emde Boas/(/lg/frac{/omega}{a}/)但当a很大时，它们会改善一些因素。
如果我们有/(O(n poly/lg n)/)空间和/(a=O(/lg/lg n)/)，则得到如下结论：
– 如果/(w=O(poly/lg n)/)，则Van Emde Boas树对小的/(/omega/)来说是最优的。
– 如果/(/lg/omega=/Omega(/sqrt/lg n/lg/lg n)/),则融合树对大的/(/omega/)是最优的。
– 在小和大的/(/omega/)之间，界为/(/Theta(min/{/log_/omega n, /frac{/lg/omega}{/lg/frac{/lg/omega}{/lg/lg n}}/})/)。

3 Communication Complexity

3.1 Communication complexity观点

我们在通信复杂性模型中考虑这个问题。在这个通用模型中，Alice知道一个值/(x/)，Bob知道一个值/(y/)。他们想共同计算某个函数/(f(x, y)/)。然而，他们被限制在一个协议中，在这个协议中他们交替向对方发送消息。此外，Alice的信息只能是/(a/)比特长，而Bob的信息只能是/(b/)比特长。我们可能期望/(x/)和/(y/)比/(a/)和/(b/)有更多的比特，所以你可能不得不发送多个信息。我们把这个问题看成是一轮一轮的通信，其中一轮是Alice与Bob通信，然后Bob与Alice通信。
将这个模型应用于着色前序问题，我们可以认为Alice是查询算法，她知道查询/(x/)。Bob内存/RAM，他知道数据结构/(y/)。 他们一起想找到/(f(x, y)/)，也就是彩色前身查询的答案。直观地说，一轮通信是一次内存读取，Alice想向Bob “询问 “数据结构中的值以便她能计算出答案。
因此，Alice的信息将是地址位，所以/(a=O(/lg(space))/)。鲍勃将返回存储在数据结构中的值，所以/(b=w/)，字的大小。每一 “轮 “通信包括两个消息，对应于cell porbe模型中的一个探针。(这是一个静态问题，所以我们只有cell porbe的读取，而不是写入。)因此，消息的数量等于cell porbe数量的两倍。如果我们能在cell porbe模型中建立一个下限，这将意味着在字RAM模型中也有一个下限。

3.2 前序的下界

定义：通信模型中需要的信息数量（也是区域cell porbe的数量）是/(/Omega(min/{/lg_a w, lg_b n/})/)。
推论：这意味着Beame-Fich-Xiao下界为/(/Omega(min/{/frac{/lg/omega}{/lg/lg/omega},/sqrt/frac{/lg n}{/lg/lg n}/})/)。
假设在多项式空间，/(a=/Theta(/lg n)/)。当/(/log_a/omega/stackrel{/mathrm{/Theta}}{=}/log_bn/)时下界最大，其中/(/stackrel{/mathrm{/Theta}}{=}/)表示在常数因子内相等。求解我们发现：

/[/frac{/lg/omega}{/lg/lg n}/stackrel{/mathrm{/Theta}}{=}/frac{/lg n}{/lg/omega}/Leftrightarrow/lg/omega/stackrel{/mathrm{/Theta}}{=}/sqrt{/lg n/lg/lg n}/Leftrightarrow/lg/lg/omega/stackrel{/mathrm{/Theta}}{=}/lg/lg n
/]

利用上述等价关系，我们重写/(/Omega(min/{lg_a/omega, /lg_bn/})/):

/[/Omega(min/{/frac{/lg/omega}{/lg a}, /frac{/lg n}{/lg/omega}/})=/Omega(min/{/frac{/lg/omega}{/lg/lg n},/frac{/lg n}{/sqrt{/lg n/lg/lg n}}/})=/Omega(min/{/frac{/lg/omega}{/lg/lg/omega},/sqrt{/frac{/lg n}{/lg/lg n}}/})
/]

这种表示方法使我们最容易看到Beame-Fich-Xiao的下界。使用上述计算中的一些中间步骤，我们也可以将该界限改写为：

/[/Omega(min/{/frac{/lg/omega}{/lg/lg n}, /log_/omega n/})
/]

这就是我们在概述中提出的形式。这种表示方法使得我们很容易看到，min函数的第一个参数看起来像Van Emde Boas复杂度（最多相差一个/(/lg/lg/)系数），而第二个参数看起来像融合树复杂度。

4 Round Elimination

让我们回到抽象的通信模型（不一定与前序问题有关）来讨论Round Elimination。Round Elimination给出了一些条件，在这些条件下，第一轮通信可以被消除。为了做到这一点，我们考虑一个任意的 “/(k/)-fold “的函数/(f/)：
定义 1：让/(f^{(k)}/)当作/(f/)的一个变体，其中Alice有/(k/)个输入/(x_1,/dots ,x_k/)，而Bob
有输入：/(y，i∈1，/dots k，/)和/(x_1，/dots, x_{i-1}（/)注意这与爱丽丝的输入重叠）。我们的目标是是计算/(f(x_i, y)/)。
现在假设Alice必须发送第一条信息。注意，她必须发送这个消息，即使她还不知道/(i/)。直观地说，如果/(a/ll k/)，她不太可能发送任何关于/(x_i/)的信息，这是她的输入中唯一重要的部分。因此，我们可以把通信协议从第二个信息开始。
引理 2(Round Elimination引理)：假设有一个f的协议/(f^{(k)}/)有一个协议，其中Alice先发言，使用/(m/)个信息，错误概率为/(/delta/)。有协议/(f/)，其中Bob先发言，使用/(m-1/)条信息，错误概率/(/delta+O(/sqrt{a/k})/)。
直观的：如果/(i/)是均匀随机选择的（这是最坏的情况），那么在Alice的第一个信息中，”关于/(x_i/) “的预期比特数是/(1/2^{a/k}/)。Bob可以随机地猜测这些比特；而猜对所有比特的概率是/(1/2^{a/k}/)，所以失败的概率是/(1-2^{-a/k}/)。因为我们对小的/(a/k/)感兴趣，串联扩展表明，/(1-2^{-a/k}≈a/k/)。因此，通过消除Alice的信息，错误概率应该增加大约/(a/k/)。在现实中，这种直觉并不完全正确我们只能将错误的增加限定为/(/sqrt{a/k}/)，取决于应用情况这通常还是可以接受的。

5 前序界证明

证明简述：设/(t/)为 cell probes的数量，或者等价地，为通信的轮数。我们的目标是应用Round Elimination定理/(2t/)次来消除所有的信息。在这一点上，必须猜出前序的颜色（假设/(n’≥2/)，如定义5.1中的定义），因此成功的概率最多为/(/frac{1}{2}/)。
如果我们能将错误概率的增加最多限定为/(/frac{1}{6}t/)，那么在每一步中应用/(2t/)的应用将使错误概率从0增加到最多/(/frac{1}{3}/)。然而，这使得成功的概率至少为/(/frac{2}
{3}/)这是个矛盾的问题。
换句话说，没有一个有/(t/)个cell probes的算法可以解决这个问题，所以/(t/)是任何静态随机染色前序数据结构预期性能的下限。

5.1 Eliminating Alice→Bob

Alice的输入有/(/omega’/)位(初始化，/(/omega’=/omega/))。将输入分成/(k=/Theta(at^2)/)等大小的块/(x_1,/dots,x_k/)，每块大小为/(/frac{/omega’}{k}/)位，如果我们能将误差的在每一步增加限制为/(O(/sqrt{/frac{a}{at^2}}=O(/frac{1}{t}))/)，然后调整常数将得到/(/frac{1}{6}t/)。
我们构建了一棵/(/omega’/)位字符串分支因子为/(2^{/frac{/omega’}{k}}/)的对应于Alice的可能输入的树，也就是数据结构的元素。然后，这棵树的高度为/(k/)。在最坏的情况下，我们可以限制/(n’/)(初始化，/(n’=n/)）的元素都在第/(i/)块中不同。Alice和Bob知道输入的结构，所以Bob知道/(i/)和所有的公共前缀元素/(x_1,/dots,x_{i-1}/)。因此，当Alice的信息被消除后，目标就变成了查询/(x_i/)中的数据结构的第/(i/)块，而/(w’/)被简化为/(/frac{/omega’}{k} = Θ(/frac{/omega’}{at^2})/)。
这种数据结构的一个类比是Van Emde Boas树，因为vEB二进制搜索的层次是找到最长的前缀匹配，并在搜索过程中减少/(w’/)。利用该定理，错误概率增加了/(O(/sqrt{/frac{a}{at^2}}) = O(/frac{1}{t})/)，这正是我们能够负担得起的每次消除的开销。

5.2 Eliminating Bob→Alice

现在，Alice的信息被消除了，Bob首先发言，所以他不知道查询的值。Bob的输入是/(n’/)整数，每个大小为/(w’/)比特。将这些整数分成/(k = Θ(bt^2
)/)相等的小块的/(/frac{n’}{k}/)整数块。记住，融合树可以在一个大小为/(/frac{n}{w^{1/5}}/)的集合中，经过/(O(1)/)个cell probes。这里，我们要证明的是，在一次探测之后，你只能递归到一个大小为/(/frac{n}{w^{O(1)}}/)的集合。这给出了相同的误差增加界限，即/(O(/frac{1}{t})/)。
为了得到下限，对输入进行约束，使第/(i/)块/(x_i/)以二进制的前缀/(i/)开始。Alice的查询从一些随机的/(/lg k/)位开始，这决定了哪个块是感兴趣的。如果Bob先说话首先，他不能知道哪个块是感兴趣的。

利用该定理，消除法将错误概率提高了/(O(/frac{1}{t})/)；减少/(n’/)到/(/frac{n’}{k} = Θ(/frac{n’}{bt^2})/)和/(w’/)到/(w’ – /lg k = w’ – Θ(/lg(bt^2))/). 只要/(w’/)不会变得太小，/(w = Ω(/lg(bt^2))/)，这最后一个项可以忽略不计（例如，它将/(w’/)最多减少2个系数）。

5.3 停止

因此，每一轮的消除都会减少/(n’/)到/(Θ(/frac{n’}{bt^2})/)和/(w’/)到/(Θ(/frac{w’}{at^2}。此外，通过选择适当的常数最后的概率误差的概率最多为/)/frac{1}{3}$。

当/(w’0=O（/lg（bt^2)）/)或/(n’=2/)时，我们停止消除。如果这些停止条件得到满足,我们已经证明了我们的下限：要么最初有很多轮，我们可以做足够的淘汰，把/(n/)和/(w/)减少到这些小值，或者我们有一个协议，可以用零消息给出答案的答案。但是，这将意味着错误概率最多为$/frac{1}{3}，这是不可能的。因此，我们必须处于第一种情况（停止条件得到满足）。

因此，我们已经建立了一个下限/(t=Ω(min/{/lg_{at^2}/omega, /lg_{bt^2}n/})/)。然而，由于/(t=O(/lg n)/)和/(a ≥ /lg n/)，我们有/(a ≤ at^2 ≤ a^3。 同样地，因为/)t = O(/lg /omega)，b = /omega/(，我们有/)b ≤ bt^3 ≤ b^3/(。 因此，我们可以得出结论：/)t = Ω(min{/lg_a /omega, /lg_b n})$。

6 Round Elimination定理的证明简述

6.1 一些信息理论基础知识

定义3: /(H(x)/)，称为/(x/)的熵，是表示随机变量/(x/)的分布的平均所需的比特数。

/[H(x)=/mathop{/Sigma} /limits_{x_0}Pr[x=x_0]·/lg/frac{1}{Pr[x=x_0]}
/]

定义4: H(x | y)是给定y的x的条件熵：如果y是已知的，x的熵:

/[H(x|y)=E_{y_0}[H(x|y=y_0)]
/]

定义5: I(x : y)是x和y之间的相互或共享信息:

/[I(x : y) = H(x) + H(y) − H((x, y)) = H(x) − H(x | y)
/]

/(I(x : y | z)/)的定义与/(H(x | y)/)相似。

6.2 The Round Elimination Lemma

称Alice的第一个信息为/(m = m(x_1, … , x_k)/)。接下来，我们利用信息论中的一个巧妙的定理将熵重写为一个总和，这可以被认为是 “信息的连锁规则”。

/[a = |m| ≥ H(m) = /mathop{/Sigma} /limits_{i=1}^kI(x_i: m | x_1, . . . , x_{i−1})
/]

如果/(i/)均匀地分布在/({1, . . , k}/)，那么/(E_i[I(x : m | x1, … , xk)] = /frac{H(m)}{k} ≤ /frac{a}{k}/)。 这就是为什么/(/frac{a}{k}/)是对Bob能从信息中了解到多少比特关于Alice的信息的估计。注意，我们限定了/(I(xi: m | x1, . . , xi-1)/)，所以即使Bob已经知道/(x_1, . . , x_{i-1}/)并收到了/(m/)，他仍然最多能学到/(/frac{a}{k}/)位的信息。

为了证明这条定理，我们必须在假定的/(f/)的协议下建立一个/(f^{(k)}/)的协议。 我们可以构建一个协议￥f(x, y)￥，如下所示：

• 固定/(x_1, . . . , x_{i-1}/)和/(i/)是先验的（双方都知道）随机的。
• Alice假设$ x_i = x$。
• 运行/(f^{(k)}/)协议，从第二个信息开始，假设第一个信息是/(m = m(x_1, . . , x_{i-1}, /widehat{x}_i, . . . ，/widehat{x}_k）/)，其中xj是一个从分布中抽取的随机变量。现在，第一个信息并不取决于/(x_i = x/)（甚至/(x_i/)是随机选择的），所以Bob可以自己生成它，而不需要从Alice那里得到任何初始信息。
• 现在Alice有一些真实的/(x/)，她必须用它作为/(x_i/)而且几乎可以肯定的是，/(/widehat{x_i} /neq x/)。我们知道，/(I(x_i: m)/)非常小，所以信息并不真正依赖于/(x_i/)。这意味着一个随机的信息可能是好的: Alice现在可以固定/(x_{i+1}, . . . , x_k/),这样对于期望的/(x_i = x/),/(m(x_1, . . . , x_{i-1}, /widehat{x}_i, . . . ，/widehat{x}_k) = m(x_1, . . , x_{i-1}, x, . . , x_k)/)。

最后一步是关键的一步，它也引入了一个错误概率为/(O(/sqrt{/frac{a}{k}})/). 这可以可以根据信息论中的 “平均编码定理 “来证明。还存在一个这个定理所解决的更微妙的问题：不仅必须存在/(x_{i+1}, …. , x_k/)的存在，使Bob对信息的随机猜测变得有效，而且它们的分布与原始分布接近，所以错误概率/(δ/)不会增加太多。