量子对抗方法与经典公式大小下界

量子对抗方法与经典公式大小下界SophieLaplanteLRI，巴黎南大学laplante@lri.frTroy LeeCWI和阿姆斯特丹电子邮件：cwi.nl马里奥·塞格迪罗格斯大学szegedy@cs.rutgers.edu摘要我们引入了两个新的布尔函数的复杂性度量，我们命名为sumPI和maxPI。quantitysumPI是通过对量子查询复杂度下限的研究而出现的，称为量子敌手方法[Amb 02，Amb 03，BSS 03，Zha04，LM 04]，最终在[SS 04]中实现这些不同的公式实际上是等价的。鉴于sumPI是一个函数的鲁棒不变量，我们开始研究这个量本身，并发现它也可以应用于经典复杂性理论。作为一个新的应用程序，我们知道，μmPI2（f）是公式大小的下限，甚至，直到常数乘法因子，f的概率公式大小。我们证明了文献中的几个公式大小的下界，特别是Khrapchenko及其扩展[Khr71，Kou 93]，在[Has98]中包含gakeylemma，实际上是我们方法的特殊情况。我们引入的第二个量maxPI（f）总是至少与sumPI（f ） 一 样 大 ， 并 且 从 sumPI 中 导 出 ， 使 得maxPI2（f）保持公式大小的下限。我们的主要结果是证明通过一个组合引理，它涉及到一个矩阵的谱范数的平方，其子矩阵的谱范数的平方。这个引理的一般性给出了我们的方法也可以用来下界关系的通信复杂性，以及相关的组合量，矩形划分数。为了展示我们的方法的优点和缺点，我们研究了几个例子的sumPI和maxPI1介绍复杂性理论中一个长期存在的中心问题是证明显式布尔函数电路规模的超线性下界。虽然这看起来相当困难，但在公式大小稍弱的模型中已经取得了适度的成功，公式只是一个电路，其中每个门最多有一个扇出目前最好的公式大小下限为显式函数isn3−o（1）byH astad[H as98]。在本文中，我们表明，部分丰富的理论德-围绕证明量子查询复杂度的下限，即所谓的量子敌手论证，可以被带到公式大小下限上这增加了越来越多的例子，说明研究量子计算如何导致经典复杂性的新结果，包括[SV01，KW 03，Aar 04，LM 04]，仅举几例。量子对抗论点的根源可以是追溯到[BBBV97]的混合论证，他们用它来展示量子搜索的一个下界。 我-贝尼斯提出了一个更复杂的对抗性论点，[Amb02]，后来将此方法改进为全强度量子对手论证[Amb03]。进一步的推广包括Barnum、Saks和Szegedy[BSS 03]及其谱方法和Zhang [Zha04]及其强对手方法。Laplante和Magniez [LM 04]使用Kol- mogorov复杂性来捕获最小化问题方面的对手论点。这条研究路线-Min at esi n recceto rk ofSp a lekand dS zeg ed y[SS04] wh o事实上，[Amb 03，BSS 03，Zha 04，LM 04]的所有方法都是等效的。量子对抗论有如此多的等价定义这一事实表明，它是布尔函数的一种自然组合性质，值得单独研究我们给这个泉-arXiv：quant-ph/0501057 v2 2005年{∈}--||≥∈联系我们∈∈≫33−−∀−≥≥−◦≥◦将其命名为sumPI，并采用该方法的以下原始形式，来自[S/S04，LM 04]。设ngS → {0，1}n和f：S → {0，1}是布尔函数，说11.1组织在第2节中，我们给出了定义，结果，和符号，我们使用整个文件，并介绍了quanti- tiessumPI，maxPI和KI。在第3节中，我们证明了一些sumPI和maxPI的性质。在第4节中，我们将展示如何sumPI（f）=min（1）第一次见面px，yf（x）/=f（y）我xi yipx（i）py（i）sumPI和maxPI产生公式大小下限，用于确定性和概率公式大小。在第二节中，其中p = px：x S是指数[n]上的概率分布族。 如果Q_（f）是满足Q_（f）=ψ（sumPI（f））的双边误差方程。我们认为，最小PI2（f）的大小小于f的最小大小。 此外，SumPI2（f）gene在文献中，特别是Khrapchenko及其扩展[Khr 71，Kou 93]中，确定了一些公式大小下限，并在[Hal98]中给出了一个关键定理，该定理用于为显式函数确定最佳公式大小下限。我们还介绍第五，我们比较了我们的新方法与以前的方法在公式大小复杂度。在第6节中，我们研究了我们和其他公式下界方法的局限性。最后，在第7节中，我们将我们的技术应用于一些具体问题。2预赛我们使用标准符号，例如[n]=1，. . .，n，S的基数，所有的基数都是2。汉明距离记为dH。KI（f）=最小值α∈Σ∗Maxx为ohf（x）mini：xi/=yiK（i| x，α）+K（i| y，α），2.1布尔函数其中K是无前缀Kolmogorov复杂度。该公式源于[LM04]的量子和随机这一表述特别有趣，因为它提供了直观性。例如，它允许一个非常简单的证明，电路深度d（f）KI（f），使用电路深度的Karchmer-Wigderson characteri- zation [KW 88]。KI我们使用布尔函数的标准度量，例如敏感性和证书复杂性。我们在这里简要地重新调用它们，更多细节见[BW02]。 对于集合S0，1n和布尔函数f：S0，1，f对输入x的灵敏度是位置i [n]的数量，使得改变位置i的x值会改变函数值。零灵敏度，写作s0（f）是我们定义一个与2密切相关的量最大PI。1我们称f−1（0）上f对x的灵敏度的最大值。单灵敏度s1（f）的定义类似。s0（f），s1（f）的最大值是f的灵敏度，记为s（f）.maxPI（f）=minMax-是的（二）f在输入x ∈S上的证书是子集I∈[n]px，yf（x）/=f（y） Maxi：xiyipx（i）py（i）使得对于任何满足yi=xi的y，对于所有i ∈ I，它必须是注意，这与sumPI类似，但其中的和被最大值替换.根据定义，maxPI大于sumPI，但其平方仍然是公式大小的下限。然而，maxPI不再是一般量子查询复杂度的下限，我们给出了一个测试-对于其中PI（f）=2且df（y）=f（x）。f的零证书复杂度，记为C0（f），是所有x上的最大值f−1（0）x的最小大小证书。类似地，f的单证书复杂度，记为C1（f）是x的最小大小证书在所有x ∈ f−1（1）上的最大值。2.2线性代数maxPI（f）= n/2。对于此功能，碰撞探测器-lem，maxPI（f ）Q（f ）=Θ（n1/3）[A S04，BHT 97].我们看几个具体的问题来说明我们的方法的优点和缺点。本文研究了三个问题R MAJh的高度h递归多数，证明了Q_（？）（R MAJh）= R_（？）（2h），公式大小的下界为4h我们还研究了由Ambainis [Amb 03]定义的函数，以将函数的量子查询复杂性与多项式方法[BBC+ 01]给出的界限这个函数给出了一个例子，其中sumPI2可以给出比Khraphchenko的界限好得多的东西我们还给出了碰撞问题的界。对于矩阵A（分别为向量v），我们写AT（分别为A是A的一种，A是A的一种，A是A的一种。v）的共轭 转 置 . 对 于 两 个 矩 阵 A ， B ， 设 AB 是 A 和 B 的Hadamard积，即（AB）[x，y] =A[x，y]B[x，y].我们写A B如果A是en-当AB 是半正定的时， A B 的值大于B ，即v ：vT（AB）v0。我们让rk（A）表示矩阵A的秩。我们将广泛使用谱范数，表示为2002年2月。对于矩阵A，Af（y）| |∗2∧∨我的天{} → {}∈∈∈∈∈∈×∈⊆× ×联系我们联系我们≤≤⊆||联系我们对于一个向量v，我们设v是v的范数。我们还将利用最大绝对值，定义为A|A[i，j]|，并且最大化了若不存在rm，则定义为ΔA_∞，并定义为ΔA_∞=maxijA[i，j]。我们收集一些关于谱范数的事实这些可以在[HJ99]中找到。命题1设A是任意m×n矩阵。然后2.4关系的沟通复杂性Karchmer和Wigderson [KW 88]给出了一个通信游戏中公式大小的优雅特征。我们将使用这个框架来展示我们的下限。这个演示文稿的优点是表明，我们的方法工作更一般的通信复杂性的关系超出了“特殊情况”的公式大小。通信复杂性的框架还允许我们使用矩形分区编号，1.2012年2月=最大u，v|u Av||u||v|ber，CD（R），这是已知的下限通信复杂性，并在使用我们的2.A3. 对于非负矩阵A，B，如果A ≤ B，则<$A_2≤<$B_22.3确定性和概率公式标准基上的布尔公式、、是一个二叉树，其中每个内部节点都标记为或，并且每个叶用文字标记，即布尔变量或其否定。公式的大小是它的叶子数。我们很自然地将公式与它所计算的定义2设f：0，1n0，1是布尔函数. f的公式大小，记为L（f），是计算f的最小公式的大小。公式深度f，记为d（f），是计算公式的最小深度。技术.设X，Y，Z是有限集，RXYZ.在关于R的通信博弈中，爱丽丝被给予X，鲍勃被给予y他们的目标是找到一个z z使得（x，y，z）R，如果z存在的话。通信协议是一棵二叉树，其中每个内部节点v由函数av：X0，1或bv：Y0，1标记，描述在该节点的Alice或Bob的消息，并且其中每个叶用元素z标记 Z. 通信协议计算R，如果对于所有（x，y）XY，根据av，bv沿着树向下走，导致用z标记的叶子，使得（x，y，z）R，假设这样的z存在。R的通信成本D（R）是计算R的最小通信协议的高度。R的通信矩阵是矩阵i xMR[x，y]={z：R（x，y，z）}。一个rect-具有X′≠X和Y′≠Y的x′T×Y′是单染色体，英湾matic ifx∈X′，y∈Y′MR[x，y]- 是的 协议部分-在L（f ）处h是清楚的2d（f ）;相反的不等式d（f）O（logL（f））也成立是Spira [Spi 71]的一个非平凡结果.我们还将考虑概率公式，即确定性公式上的概率分布。我们采用概率公式大小的最坏情况概念。之前已经研究了概率公式大小，例如在[Val 84，Bop 89，DZ97，Kla04]中。其中，P（R）是指在较小的范围内的叶数。est通信协议计算R，矩形分割数CD（R）是覆盖X×Y所需的最小不相交单色矩形数。(NoteCD（R）≤CP（R）。定义4对于任何布尔函数f，我们关联关系Rf={（x，y，i）：f（x）= 0，f（y）=1，xiyi}。定理5（Karchmer-Wigderson）任何布尔定义3设{fj}j∈J 是一组函数fj：在f上，L（f）=CP（Rf），d（f）=D（Rf）。对于每个j ∈ J，S→ {0，1}。 对于函数f：S →{0，1}，我们说f被{fj}j ∈ J逼近，如果存在J上的概率分布α ={αj}j∈J，使得对于每个x ∈ S，Pr[f（x）=fj（x）]≥1−k。特别地，如果maxjL（fj）≤s，那么我们说f是由大小为s的公式来近似的，记为L<$（f）≤s。请注意，即使函数依赖于其所有变量，概率公式的大小也可能小于变量的数量。2.5sumPI和量子对抗方法阅读本文不需要量子计算的知识;然而，为了完整性，我们简要地概述了量子查询模型。关于量子查询复杂性和量子计算的更多背景可以在[BW02，NC00]中找到。与经典的对应模型一样，在量子查询模型中，我们希望计算某个函数f：S 0，1，其中Sn，并且我们通过查询访问输入。f的复杂度是计算f所需的查询数量。然而，与经典情况不同，我们现在可以α∈ ∈ {}/||×||联系我们联系我们···−××Σ{∈}联系我们联系我们{∈ ∈}||⟨⟩|√Max在叠加中进行查询。形式上，查询O对应于酉变换阿：|i，b，z |i，b xi，z其中i[n]，b0，1，z表示工作空间。t-查询量子算法A具有形式A=我们还将使用光谱对抗方法。定义8（谱附加）设S0，1n且f：S0，1 是一个布尔函数设X=f−1（0），Y =f−1（1）. 设Γ = 0是任意XY非负对称矩阵，当f（x）= f（y）时，满足Γ[x，y] = 0. 对于i ∈ [n]，设Γi为矩阵：Ut0，其中Uk是固定酉的变换独立于输入x。 该计算机-Γi[x，y]=.0ifxi=yi从国家开始|0 π，计算A的结果是A的最右边位的观测值|0分。然后Γ[x，y] ifxiyiǁΓ ǁ我们说，如果观察到的A的最右位|f（x）的值为0，SA（f）=maxΓ2最大值iri21、对于每个x。我们用Q（f）表示量子查询算法的最小查询复杂度，它是f的-近似。随着 多项式方法[BBC+ 01]，一个请注意，谱对抗方法最初是针对X ∈ Y上的对称矩阵定义的[BSS 03]。上面的定义是等价的：如果A是一个X<$Y矩阵sat-当f（x）=f（y）时，在A∈[x，y]=0时，显示量子查询复杂度下限的主要技术之一是量子敌手则A具有形式A=0字节BT0对于一些矩阵，方法[Amb 02，Amb 03，BSS 03，Zha 04，LM 04]。最近，S palekanddSzeg ed y[SS04]已经表明，量子对抗方法的所有强版本都是等价的。alent，并进一步指出，这些方法可以很好地表征为原始和双重。我 们 给 出 的 原 始 特 征 作 为 我 们 的 主 要 定 义 的sumPI。定义6（sumPI）设S ∈ {0，1}n且f：S → {0，1}B除以XY则A的谱范数等于B的谱范数。类似地，对于任何XY矩阵A，我们可以形成A的对称化版本，如上所述，保持谱范数。我们经常隐式地使用下面的定理，以便对我们希望证明的特定界限采取最方便的方法定理9（S_palek-S zeg edy）Letn≥1是一个不等式，是一个布尔函数对任意x ∈ S，设px：[n]→R是一个概率分布，即px（i）≥0且ipx（i）= 1. 设p = px：xS。我们定义指数和概率为sumPI（f）=minmax1S → {0，1}n且f：S → {0，1}。然后sumPI（f）=SA（f）=PA（f）2.6KI和maxPI复杂性度量KI的定义来自Kolmogorov com-px，yf（x）f（y）ipx（i）py（i）x/=y复杂对手法[LM 04]。 科尔莫戈罗夫的com-我我我们还将使用两个版本的对偶方法，重量计划和频谱制定。对我们来说，最方便的定义7（概率方案）设S0 ， 1n 和f：S0，1是布尔函数，且X=f−1（0），Y=f−1（1）。设q为X×Y上的概率分布，pA，pB分别为X，Y上的概率分布. 最后设{p′x，i：x ∈X，i∈[n]}，皮伊岛 ：y是的，我[个] 是概率分布族X、Y上的分布。 假设q（x，y）= 0一个字符串x的复杂度CU（x），关于一个泛图灵机U是最短程序p的长度，使得U（p）=x。给定y的x的复杂度，记为C（x，y）是最短程序p的长度，使得U（p，y）=x。当U使得输出的集合是无前缀的（集合中没有字符串是集合中另一个字符串的前缀）时，我们写为KU（x y）。从这一点开始，我们固定U，简单地写K（x y）。关于Kolmogorov复杂性的更多背景请参考[LV97]。定义10令Sn表示字母表。对于任意函数f：S→{0，1}，设当f（x）=f（y）时。 设P在所有可能的元组KI（f）=最小值x为ohmin K（i| x，α）+K（i|y，α）。（q，pA，pB，{p′x，i}x，i）的分布。然后α∈Σ∗ f（x）f（y）i：xiyiPA（f）=maxPminx，y，if（x）/=f（y），xi/=yi.pA（x）pB（y）p′x，i（y）p′y，i（x）q（ x，y）使用基于Kolmogorov复杂性的概念的优点是，它们通常自然地捕获下界的信息理论内容。作为一个例子，我们给出了一个简单的证明，KI是电路深度 的 下限。/||≤||||≤{∈}⊆ ∈→≤{} → {}联系我们定理11对任意布尔函数f，有KI（f）≤ d（f）.证明：设P是R f的一个协议。在f下用不同的值固定x，y，并让TA是从A发送到B的消息的转录，在输入x，y上。类似地，设TB是从B发送到A的消息的脚本 设i为协议的输出，其中xi=yi。要打印给定x的i，使用x和TB模拟P。要打印给定y的i，请使用y和TA模拟P。这表明x，y：f（x）f（y），i：xi=yi，K（ix，α）+K（y，α）TA+TBD（Rf），其中α是A和B算法的描述。Q引理14设g1，. . . ，gn是布尔函数，h是函数，h：{0，1}n→{0，1}. 若sumPI（h）≤ b，则对f = h（g1，. . . ，gn），sumPI（f）≤ab.证明：设p是一个最优分布函数族，它与h和pj是与gj相关联的最优分布函数族。 定义分布函数qx（i）=pg（x）（j）pj，x（i）.j∈[ n]一个类似的证明事实上表明，KI（f）≤假设对于x，y ∈ S，我们有f（x）f（y）。是2N（Rf），其中N是第二个非线性系统，足以说明复杂性由于边界没有利用两个参与者之间的相互作用，在许多情况下，我们不能希望得到最佳的下界使用这些技术。在[S04]中的一个简单的例子是，- 是的-是 的Σpg（x）（j）pj，x（i）pg（y）（j）pj，y（i）i：xiyij∈[n]j∈[n]2KI（f）.= Θ minΣ1最大值1≥ab。（三）px，yf（x）f（y） Maxipx（i）py（i）由柯西-施瓦茨，方程的左手边。 3是请注意，方程的右侧与sumPI的定义相同，只是分母中的和被最大值取代。这使得我们定义了复杂性度量maxPI，以获得更强的公式大小下限。定义12（maxPI）设f：S → {0，1}为函数大于或等于好吧.pg（x）（j）pj，x（i）pg（y）（j）pj，y（i）i： xi yij∈[n]- 是的- 是的与S。 对于每个x S，设px：[n]R是一个概率分布。设p=px：x S。我们定义指数的最大概率为=j∈[ n]pg（x）（j）pg（y）（j）i： xiyipj，x（i）pj，y（i）.（四）当g∈j（x）/=g∈j（y）时，通过对p∈j的定义，我们maxPI（f）=min1最大值有i：xiyipj，x（一）pj，y（i）≥1/a。 因此我们可以-px，yf（x）/=f（y） 麦克斯我px（i）py（i）在Eq中估计表达式4从下面：它可以很容易地从定义的条件上得到，对于任何f，都是sumPI（f）maxPI（f）。下面的引理也是从定义中直接得出的：1Σ一j：gj（x）/=gj（y）.pg（x）（j）pg（y）（ j）。引理13若S′→S且f′：S′→ {0，1}是f：S→{0，1}对S′的整环约束，则sum PI（f ′）≤sumPI（f）且maxPI（f ′）≤maxPI（f）.3sumPI和maxPI的性质3.1sumPI的性质虽然一般来说，正如我们将看到的，sumPI给出的公式大小下限比maxPI弱，但sumPI的度量通过p的定义，我们可以估计和（没有1/a系数）从下面通过1/b，完成证明。Q使用sumPI复杂度的另一个优点是Ambainis [Amb03]的以下非常强大的引理，它可以很容易地降低迭代函数的sumPI定义15令f： 0，1 n0，1是任何布尔函数.我们定义f的第d次迭代，写作fd：它有几个很好的性质，使它在实际中使用更方便。{0，1}nD→ {0，1}，归纳为f1（x）=f（x），下一个引理表明，sumPI在函数的合成方面表现得像大多数其他复杂性度量一样：fd+1（x）= f（f d（x1，. . . ，xnd），f d（xnd +1，. . . ，x2nd），. . . 、fd（x（n-1）nd+1，. . . ，xnd+1））1/∈ ∈∈- -x为ohp （i）p（i）我 我我我≤ ∈∈引理16（Ambainis）设f是任意布尔函数，这是一个很好的例子。 则sumPI（f d）≥（sumPI（f））d。证明：对于一个固定的概率分布族p={px}，对于表达式结合引理14，我们得到：MaxMax（5）f（x）f（y）i：xiyix y推论17设f是任意布尔函数，且fd是第d个让我们定义索引选择函数P[x，y] = 1，如果这是一个没有F的时间。 sumPI（fd）=（sumPI（f））d。吉吉i=argmaxi：xiyipx（i）py（i）and d 0 ot erw is e.（Arg max引理13和14以及Grover搜索的对手论证下界[Gro96，Amb02]是表达式获得其值的最小参数maxi maldrouva lu e.） 但在E q中没有任何人。5BECOME这意味着对于全部布尔函数，等于i：xi/=yipx（i）py（i）Pi[x，y]. 如果我们把它放回去块灵敏度是sumPIcom的下限P的一个较好的系统是，它使您不必选择索引索引复杂性[Amb02]。 [NS 94，BBC+ 01]：函数的值i：xiyipx（i）py（i）Pi[x，y]将不引理18（Ambainis）对于全布尔函数，sumPI复杂度与各种增加因此，我们可以重写Eq。5作为1麦克斯，（确定性的，随机的，量子的）决策树复杂性和函数的傅立叶度。x为ohf（x）f（y）max{Pi}ii：xi/=yipx（i）py（i）Pi[x，y]3.2maxPI的性质当Pi[x，y]运行时，将所有线性索引从func中删除，选项。由此可见：maxPI（f）=使sumPI如此方便使用的一个原因是，[S/RES /04]。在这个领域，我们将尽可能地利用它，- 是的表达式maxPI。最后的表达式仍然是一个最小化问题，但我们最小化离散指数选择函数，而不是家庭的概率分布。1最大最小px，yf（x）f（y）Max{Pi}ii：x/=ypx（i）py（i）Pi[x，y].（六）bitions，这使得它更容易处理。尽管如此，我们还是要注意maxPI可以花费指数时间（在f的真值表的大小中），而sumPI需要多项式时间注意，在Eq.6最小值可与第二最大值互换 其原因是，对于一个fixedpthashere是一个fixed{Pi[x，y]}，它最大限度地简化了在f的真值表的大小上，通过减少到半定规划来计算i：xi=yi由此可见：px（i）py（i）Pi[x，y]对于所有x，y：f（x）maxPI（f）=f（y）。定义19（索引选择函数），J.f：{0，1}n→ {0，1}是布尔函数，X=f−1（0），1最大值minp（i）p（i）P[x，y].Y=f−1（1）. 对于i ∈[n]，设Di为|X| ×| Y|定义{Pi}ipx，yx y if（x）/=f（y）i：xiyibyDi[x，y]=1−δxi，yi. 我们讨论了n个Boolea n（0−1）矩阵{Pi}i∈n个指标选择函数的集合，如果根据Spalek和Szegedy的maithe oremoro of，我们可以创建上述的半定版本1. CUP=E，其中对于每个x，E[x，y] = 1 ∈X，YY。（非正式地：对于每个xX，yY，我们选择唯一索引）2. PiDi（非正式地：对于每个x X，yY，我们选择的索引是i，使得xiyi）。将Pii（索引选择函数）视为我们要最大化的半定系统不幸的是，它也出现在最终表达式中。maxPI的半定版本：对于固定的{Pi}i，设μ′max请注意，索引选择函数对应于par-index。是以下半定规划的解：如果x，y在第i部分，则xi/=yi。定理20（maxPI的谱敌手版本）设f、X、Y如前面的定义。设A为任意数|X| ×| Y|满足A[x，y] = 0的非负矩阵最大限度地服从µ′中文（简体）Ri≥0，iRiiRi∈ Pi≥ μ′F。当f（x）=f（y）时。然后maxPI（f）= min max表情然而，这里的区别在于，我们必须≤ ≤{Pi}i 一2002年2月，最大值iAPi2将µmax定义为µ′max的最大值，其中Pi（1in）贯穿所有索引选择函数。则maxPI =1/µmax。我们可以把上面的程序二元化，其中{Pi}i贯穿所有索引选择函数。对于这种情况，方法与在S语言中进行查找和选择相同--→ǁǁ||maxS∈Sµ（S）唯一的变化是Di需要用Pi代替，并且我们必须在所有的选择中最小化{Pi}i.Q设u_R为u_R的行对应于u_R的行的部分，v_R为v的对应于R.注意，uRR∈R一般不形成u的一个划分。我们现在有4公式大小下限...ǁAǁ2=..乌加河≤RΣ |u A R v R|R..R∈R..R∈RKarchmer和Wigderson [KW 88]给出了一个通信游戏中公式大小的优雅特征。我们将使用这个框架来展示我们的低Σ≤R∈RR102| uR|| vR|界限。本演示文稿的优点是表明我们的方法更普遍地适用于社区，提案1。 应用因此，我们得到超越“特殊情况”的关系的复杂性公式大小。 通讯综合体的框架-.0.05。 Σ Σ21/22 2ity还允许我们处理一个组合量，即矩形划分数CD（R），这是已知的产品规格R∈RR102R∈R|u|v R |.|.降低通信复杂度，现在只需观察一下，在使用sumPI时，Σ Σ Σ2 22 2 2 24.1关键组合引理R∈R|u|v R|vR|=R∈R（x，y）∈Ru[x]v[y]为|u||v|=1，我们首先证明了一个组合引理，这是我们的主要结果的关键。这个引理将矩阵的谱范数平方与其子矩阵的谱范数平方联系起来。这个引理也可能是独立的兴趣。设X和Y是有限集合。一个集合系统S（在X×Y上）称为覆盖，如果S∈SS=X×Y。进一步地，如果S是覆盖，并且来自S的任何两个不同集合的交集是空的，则S将被称为划分矩形（在X×Y上）是X×Y的任意子集，其形式为X0×Y0，其中X0<$X和Y0<$Y是某个。一个集合系统R将是如果R是一个划分，并且每个R ∈R是一个矩形，则称为矩形划分设A是一个矩阵，其行从X索引，列从Y索引，设R是X×Y的一个矩形划分。 对于矩形R=X0×Y0∈R，设因为R是X×Y的一个分拆。Q4.2确定性公式在本节中，我们证明了我们的主要结果，即maxPI是公式大小的下界。我们首先确定两个自然属性，这是足够的函数是一个公式大小下限。定义22函数μ：2X×YR+称为直角测度，如果下列性质成立。1. （Subadditivit y）Foranyrectangl epartitionRofAR是|x0的|×| Y0| A的子矩阵对应于X×Y，μ（X×Y）≤ R∈Rμ（R）.矩形河对于子集S <$X×Y，我们定义：2。 （单调性）对于任何矩形R <$X×Y，且A∈S[x，y]=A[x，y]，如果（x，y）∈S且0或e.（七）S的子集S <$X×Y，如果R <$S，则μ（R）≤ μ（S）。不需要为接收器R设置时间，即可实现接收器和接收器R的差异定理21意味着，对于任何|X| ×| Y|矩阵A，具有非正则项S→||一个人||ofexpre ssio n(7)isarec t-只有一组全零的行和列。 我们现在准备陈述引理：引理21设A是任意的|X| ×| Y|矩阵（可能有互补矩阵），以及X × Y的Rapartition。Then我是说你。其他示例将为您提供任何域上的任何矩阵A（见5.4节），以及[KKN 95]的μ-矩形大小边界。设S1，S2是同一论域上的两个集合族A我们说S1嵌入在S2中（S1<$S2），如果对于每个2R∈R2S ∈S1存在一个S′∈S2使得S <$S′.证明：由命题1，A2= maxu，vu<$Av，其中最大值取所有单位向量u，v。让u，v成为单位向量实现了这个最大值。然后我们有定理23设μ是2X×Y上的矩形测度，SR是X×Y的一个覆盖，R是X×Y的一个矩形划分Σ=.uv. =.u AΣv..ǁAǁ 2= |u Av|. .- 是的.....你好 ...阿斯 图里 亚 斯河这样，R是然后|R|≥µ（X×Y）。.R∈R...R∈R证明遵循μ的次可加性和单调性。Σp（i）p2⊆ × ǁǁ--- -≥−/C 2∩≤定理24（主要定理）定义pxΣ（i）=j∈Jαjpj，x（一）. 设x，y满足sumPI2（f）≤maxPI2（f）≤CD（Rf）≤L（f）f（x）f（y）。- 是的px（i）py（ i）我问题：我们已经看到，在sumPI2（f）≤maxPI2（f），xi yi- 是的- 是的ΣCD（Rf）≤L（f）从Karchm er- W i gder s o n开始流=αjpj，x（i）ij∈ Jj∈Jαjpj，y（i））公式大小的通信游戏表征，因此xi/=yi..我们求出了满足条件ymaxPI2（f）≤CD（Rf）.设R是Rf的单色矩形剖分Σ Σij∈Jx，yαjpj，x（一）Σj∈Jx，yαjpj，y（一）苏奇特哈|R| =CD（Rf），且设A为任意的xi/=yiΣ - 是的.|×| Y|非负实数矩阵|matrix with nonnegative realentries.对于R ∈ R设color（R）是最小指数c，使得xc/=yc对所有（x，y）∈ R成立. 假设每个R都是单色的，我xi yi j∈Jx，yαjpj，x（i）αjpj，y（i）因此存在这样的颜色。定义Sc= λcolor（R）=cR.Σ=j∈Jx，yαjΣixi/=yi.j，xj，y（i）则R自然嵌入在覆盖{Sc}c∈[n]中。ForanySXY，letµA（S）=2. 根据引理21和命题1的第3项，μA是矩形测度。根据定理23，2012年2月D1-2000，S在第三步中，我们使用了Q这个引理立即表明，Max一2maxcAS2≤C（Rf）。可以给出概率公式大小的下限我们已经展示了一个特定的索引选择函数，Scc，这个不等式成立，因此它也成立maxPI2（f），这是所有索引选择函数的最小值。Q4.3概率公式sumPI的属性允许我们表明，它可以用来降低概率公式的大小。引理25设<1/2。若f：S → {0，1}是由f ∈ s{fj}j∈ J的一个函数表示的，其中对于j ∈J，umPI（fj）≤s，则umPI（f ）≤s/（1−2π）.证明：假设存在概率分布定理26设S ∈ {0，1}n，f：S → {0，1}.然后L（f）≥（（1−2）sumPI（f））2forany<1/2.证明：假设fjj∈J给出f的一个-逼近。 在反命题中使用引理25意味着有x存在somej∈J，其中hsumPI（fj）≥（1−2<$）sumPI（f）。在24h（（1（f））2它给出了定理的陈述。Q5方法之间的比较在本节中，我们将研究几种公式大小下限技术，并将它们与我们的方法进行比较公式大小下限的一个瓶颈似乎已经超越了只考虑对的α= {αj} j∈J 在Pr[f（x）=fj（x）]≥1−1时，胡氏（x，y），其中f（x）=f（y）具有汉明距离1. 事实上，Khrapchenko，Koutsoupias和对于有限个x∈S，l∈ gJx={j∈J：f（x）=fj（x）}，我们有v∈j∈Jxαj≥1−∞。 因此，对于一个yx，y∈S，我们有vej∈Jx <$Jyαj≥ 1 − 2 <$。 为方便起见，我们将Jx，y记为JxJy。由于PI（fj） 是一个具有可编程性的家族，如果fj（x）fj（y）为零，Hamming_st_ad的例子也可以被视为sumPI方法的特殊情况，其中仅考虑Hamming距离1的对5.1赫拉普琴科Σixi/=yi≥≥≥.pj，x（i）pj，y（i）≥1/s.显示公式大小下限的最古老和最通用的技术之一是Khrapchenko≥≥•联系我们--×}| |×||2⊆ ⊆ {∈{} → {}2∈--∈|联系我们≥方法[Khr71]，最初用于给出奇偶函数的紧N（n2）该方法考虑一个二部图，其左顶点是f的0-输入，其右顶点是1-输入。给定的边界是左右两边的平均度的乘积。定理27（Khrapchenko）设S ∈ {0，1}n且f：S →{0，1}.设A <$f−1（0）和B <$f−1（1）。 设C是（ x ， y ） ∈ A×B 且 汉 明 距 离 为 1 的 集 合 ， 即C={（x，y）∈ A×B：dH（x，y）= 1}.则L（f ）sumPI（f）2|C|2.|一||B|赫拉普琴科的方法可以很容易地被看作是概率方案的一个特例。假设A、B、C如定理陈述中所示，我们建立概率分布如下：• pA（x）=1/|一|对所有x∈A，pA（x）=0， 否则• pB（x）=1/|B|对所有x∈B，pB（x）=0， 否则• q（x，y）=1/|C|对所有（x，y）∈C，q（x，y）=0，否则px，i（y）=1，如果（x，y）C，否则xi=yi，0.注意，这是一个概率分布，因为对于每个x，在（x，y）∈C处，只有一个y，并且xi=/yi。根据定理9和定理24，5.3有没有什么方法布尔公式的收缩指数是最小上界γ，使得在每个变量以概率p自由的随机限制下，布尔公式从大小L收缩到期望大小pγL。确定收缩指数是重要的，因为Andreev [And87]定义了一个函数f，其公式大小为L（f）=n1+γ 。H abestad[H abestad98]showtheshrink a geeeexpone ntofBoolean formulations is 2，从而获得了n3公式大小下限（直到对数因子），这是显式函数已知的最大界。 在得到这个结果的过程中，Has首先提出了一个关于公式大小的下限的概念，该下限取决于某种形式的限制出现的概率。 他证明了这个引理是Khrapchenko方法的推广;我们在Haprist和d的引理中给出了一个具体的例子。由于我们的方法乍一看似乎与广告方法完全不同，但令人惊讶的是，它实际上是我们技术的一个特例。定义29对于任何函数f：{0，1}n→ {0，1}，1. 限制是一个0，1，n中的字符串，其中n表示变量是自由的，0或1表示变量已设置L（f）≥minpA（x）pB（y）p′x，i（y）p′y，i（x）=|2|2分别为常数0或1ρx，y，if（x）/=f（y），q（x，y）|B||B|2. 限制函数f| 是保留下来xi yi中间的表达式是sumPI（f）2.5.2 Koutsoupias边界Koutsoupias [Kou93]用谱版本扩展了Khrapchenko的方法。对于汉明距离为1的具有不同函数值的输入对，权重始终为1，其他地方为0。定理28（Koutsoupias）设f：0，1 n0，1，设Af−1（0），Bf−1（1）。设C=（x，y）一 B ：dH（x，y）= 1。 设Q是BA矩阵Q[x，y] =C（x，y）其中C与其特征函数相同。 则L（f）≥sumPI（f）2≥<$Q<$2。证明：从sumPI的谱版本可以很容易地得出该界。设Q为定理陈述中的那样在ρ中的非线性变量固定之后。3. Rp是对f的变量的随机约束的分布，通过独立地将每个变量以概率p设置为0或1，并以概率（1−p）设置为0或1而获得。4. 滤子是一组约束，它具有这样的性质：如果ρ是，则通过将其中一个ρ固定为常数而得到的每个ρ ′也在ρ中。5. 当p从上下文中已知时，对于任何事件E和任何过滤器，我们写Pr[E|表示Prρ∈Rp[E| ρ ∈ ρ]。The or em30（Hast ad，Le mm a4. 1）Letf：0，1n0，1。 设A是Rp中的随机限制将f减少到常数0的事件，B是Rp中的随机限制将f减少到常数1的事件，并且设C是随机限制ρ Rp使得f ρ是单个文字的事件。然后请注意，由于我们只考虑汉明距离为1的对，因此对于Qi的每行和每列，最多有一个非零项，最多为1。根据命题1，我们有<$Qi<$2≤ <$Q1<$Q∞≤1。现在定理如下L（f）P r[C|]2P r[A|P r[B|]. 1−p22个p2定理24Q证明：我们证明了定理遵循概率方案（定义7）。在这个证明中，我们只考虑从R p得到的限制，这些限制在滤子中。我们、联系我们→Pr[A|]≤01|也滥用符号并使用A和B来表示分