收缩引起的傅立叶浓度与德摩根公式相关

{}→{−}{}→{−}∈√√--⊆-Σ收缩引起的傅立叶浓度加州大学圣地亚哥分校计算机科学系La Jolla，CA 91097-0114，美国russell@cs.ucsd.edu瓦伦丁·卡巴涅茨西蒙弗雷泽大学计算科学学院加拿大不列颠哥伦比亚省伯纳比V5A1S6kabanets@cs.sfu.ca翻译后摘要-对于布尔函数计算的德摩根公式的次二次大小或只读德摩根公式，我们证明了一个尖锐的浓度的傅立叶质量的“小度”系数。对于布尔函数f：0，1n1，1可由de Morgan计算，公式的大小s，我们表明，las [46，2，18，43，33，34]，结果也是有用的 用于为相同的电路类设计这样的算法。我们给出了另一个例子之间的连接随机限制和小德摩根公式的算法。我们表明，对于小的德摩根公式，这是类似于傅立叶A [n]：|一|>s1/r+ef∈（A）2≤exp（−sc/3），Linial、Mansour和Nisan的著名论文中所示的AC0电路的浓度[36]。更多前-其中，r是相应类别的公式的收缩指数：对于德摩根公式，r = 2，并且r =1/log 2（5 1）3。27个一次读取的德摩根公式。我们证明，这个傅立叶浓度基本上是最佳作为应用，我们得到了次二次型大小的de Morgan公式与宇称的相关性可以忽略，在均匀分布下是可学习的，并且在次指数时间内是可压缩的.最后，我们建立了平均灵敏度的严格的Θ（s1/Γ）大小为s的只读形式ula;这反映了已知的一般平均灵敏度的严格界限Θ（s） 大小为s的德摩根公式。德摩根公式，只读德摩根公式，收缩指数，傅立叶分析，收敛范围，可学习性，压缩性，平均灵敏度I. 一、生产在过去的30年里，有许多关于复杂性和算法之间相互作用的引人注目的例子。我们知道计算困难的问题对于构建安全的密码系统[6，55，19]和去随机化[37，3，25，49]是有用的。对另一方面，电路下界是由SAT [30，29，52，53]或多项式恒等式测试[26]的非平凡算法所还观察到，用于证明现有电路下界的技术通常用于设计学习算法[36]，SAT算法[57，43，44，23，5，9，10]和伪随机数。多随机生成器（PRG）[8，24，16，48]对于同一类电路。特别是，随机限制的方法，用于证明对AC0电路[14，56，17]和德摩根公式的下界。利用随机约束下的deMorgan公式的集中收缩，证明了这类公式的大部分Fourier质量都集中在低权系数上.这里集中收缩意味着公式在受到随机限制时以高概率收缩。如此集中的收缩 [24]（考虑了伪随机限制的情况）隐含地证明了这一点，建立在[20，18]的早期“期望收缩”结果的基础上作为这种傅立叶浓度的直接结果，与[36]类似，我们获得了针对奇偶校验的强相关下界，均匀分布下的学习算法，以及一般de Morgan公式和只读deMorgan公式的平均灵敏度界（只读公式具有更好的参数）。我们接下来提供更多细节A. 我们的结果1) 傅立叶浓度和相关边界：布尔函数f：0，1n1，1的傅立叶变换是一种在函数χ S（x1，. . .，xn）=（1）i∈Sxi，在所有子集S[n]上. 直觉上，在基函数χS处的f，记为f（S），f与输入x i上的奇偶校验函数之间的相关性，对于i S。因此，人们会期望奇偶函数难以计算的电路类别在高权重上不会有太大的权重大集合S的度傅立叶系数f（S），即，这种电路将在低阶系数上表现出傅立叶频谱的集中第一个这样的联系之间的复杂性计算奇偶性和傅立叶浓度显示≈{}→{−}−−≈−∈{}→{−}联系我们{}→{−}{}→{−}1/ r+e1/ r+e√由Linial，Mansour和Nisan [36]，基于AC0电路对奇偶函数的强平均情况下限[17]。我们扩展了[36]的方法次二次型大小的德摩根公式的情况下，不能计算奇偶函数在最坏的情况下[31]，甚至平均（如下从量子设置工作[4，41]）。我们的主要结果如下。定理I. 1. 设f：0，1n1，1是一个布尔函数，可通过大小为s的德摩根公式计算。然后，对于任何常数0 <<<$1/2和任何足够大的s，下面的定义。我们显示的傅立叶浓度立即产生大小为s的一次读取德摩根公式的平均灵敏度的上限s1/Γ+o（1），其中Γ 3。27是只读公式的收缩指数。然而，我们证明（感谢Nitin Saurabh 的个人交流），可以从[7]中获得更强的上界O（s1/Γ）然后，我们证明了匹配的下界<$s（s1/Γ）。结合已知结果，德摩根公式，这产生了收缩指数和（通用和只读）德摩根公式类的平均灵敏度之间的以下紧密联系。A[n]：|一|>s1/r+ef∈（A）2≤exp（−s∈/3），推论一.2. 令f： 0，1 n1，1是一个布尔函数，可通过德摩根公式计算，其中，r是对应类的m阶：对于de Mor gan公式，r=2，S. 则AS（f）≤ O（s1/Γ），其中Γ是收缩率对应于形式u∈as：Γ=2的类的指数r = 1/log 2（5 − 1）<$3。27个是一次读的德摩根2、《易经》中的《易经》，《易经》中的《易经》（ 5−1）公式。换句话说，这意味着我们有一个非常好的近似（在l2范数下）大小为s的德摩根公式，其多项式的次数约为s1/Γ，其中Γ是这类公式的收缩指数。我们还证明了我们的傅立叶浓度本质上是最优的（引理V.3）。作为定理I.1的一个直接推论，我们得到，对于输入的大于1/2+exp（s≠/3）的分数，任何方法都不能正确地计算n大小为s n2/（1+2<$）≤n2（1−<$）的德摩根公式，对于任何常数0<<$1/2。2) 学习和压缩：作为这种傅立叶集中的结果，我们得到，类似于[36]，大小为s的德摩根公式类可以在时间ns内学习在误差范围内exp（s（）），在均匀分布上，其中对于一般的de Morgan公式，Γ = 2，而对于一般的de Morgan公式，27对于只读德摩根公式（见定理VII.2）。这类公式在[9]的意义下也是有耗可压缩的。也就是说，给定一个布尔函数f：0，1n1，1，它被保证可以用大小为s的未知的德摩根（只读）公式计算，我们可以在确定性时间内计算2O（n），一个大小为ns的布尔电路C，其中r是对应的收缩-年 龄 指 数 ， 使 得 C 在 n 位 输 入 的 除 了 exp（n<$（1））部分之外的所有部分上与f一致。3) 平均灵敏度：非正式地，布尔函数f：0，1n1，1的平均灵敏度，表示为AS（f），测量典型输入x 0，1 n中有影响的坐标的数量，其中坐标i[n]是有影响的，如果翻转第i个x中的位翻转值f（x）;我们给出一个更正式的3 .第三章。27个一次读取的德摩根公式。平均灵敏度（s1/r）可以通过r r = 2时的大小s de Morgan公式和r= 1/log2（5−1）3时的只读公式来实现。27岁。B. 我们的技术我们的出发点是来自[36]的结果，其将给定布尔函数f的如果一个随机约束可能有少于t个变量（对于某个参数t），那么所有次数至少为t的傅立叶系数都为零（因为因此，如果我们在随机限制下给定类公式的这种方法直接适用于读的情况一旦de Morgan公式，已知在“伪随机”约束下以高概率收缩然而，对于一般的德摩根公式的情况Σ||·--这种“高概率”收缩结果根本不是真的。这个问题是由“重”变量的存在造成的，这些变量在给定的公式中出现得太频繁。随机限制的概念需要可以修改，以便重变量总是受到限制，而其余的每个轻变量被选择为以某个概率p受限。我们将上述[36]的结果适用于这种修改后的限制设置。尽管如此，为了得到强傅立叶集中，需要随机约束的参数p，相当小（例如，n/ n），而[24]的已知收缩结果仅适用于相对较大的p(e.g.、p > n-1/8）。解决方案是递归地应用一些限制，每个限制都具有相对较大的值所以π的乘积幸运的是，原始函数的傅立叶谱与其相应的随机限制之间的联系很好地符合这样一个递归论证。为了证明我们的傅立叶浓度的最优性，我们展示了一个家庭的小德摩根公式，具有非平凡的相关性的奇偶函数。粗略地说，构造的公式计算输入变量的小的不相交子集的奇偶校验的AND（见引理V.3）。学习和压缩结果直接遵循傅立叶集中，使用标准方法（参见[36]）。对于一次读取公式的平均灵敏度的下限，我们使用由[39]构造的一次读取公式的显式族（建立在[51]上），其已知是抗收缩的。我们证明了相同的只读公式的大小s有平均灵敏度<$（s1/Γ）（见定理VII.5）。C. 相关工作对于大小为s的deMorgan公式，Ganor，Ko-margodski和Raz [15]证明了上界A>s1/ 2/λfλ（A）2≤O（λ），这对于常数是紧的0. 事实上，正如其中一位参考文献，一个更强的结果（匹配我们的定理I.1德摩根公式）可以推导出一些关于量子力学的研究[15]。特别地，量子查询复杂度[13，1，42，40]的结果意味着每个de Morgan公式大小为s的F可以近似为以下多项式：度D≤O（t s1/2+o（1）），逐点误差至多为2−t，因此在l2范数中也有相同的误差2−t。很容易看出，这意味着F在D次以上的傅里叶谱至多为2−t。设置t=s产生所需的傅立叶浓度如定理I.1。相反，我们的定理I.1是用经典（非量子）论证证明的，并且表现出深刻的联系。傅立叶浓度参数之间的关系，一类公式和同一类公式的收缩指数;上述量子结果（基于逐点多项式近似）不区分只读公式和通用德摩根公式。Lee [35]表明（基于量子环境中的长期工作[4，13，1，42，40]），每个de Morgan大小为s的公式可以被计算为次数为O的多线性多项式p的符号（p）（s）。特别是这完全解决了O'Donnell的一个猜想Servedio在[38]的会议版本中提出，这意味着可由大小为s的德摩根公式计算的布尔函数在时间O（n×s）内是PAC可学习的。对于一般的德摩根公式，这比我们的均匀分布学习结果，因为它适用于任何分布。另一方面，我们的证明是完全经典的，我们也得到了一个更好的运行时间的情况下读一次公式。一般来说，大小为s的德摩根公式来自[45，35]的工作（使用量子方法）;[15]也给出了另一种（经典）证明。对于大 小 为 s 的 只 读 公 式 ， 平 均 灵 敏 度 的 上 限 O（s1/Γ），其中Γ是只读公式的相应收缩指数，在[7]的工作中是隐含的。Nitin Saurabh提出了这一意见[个人交流，2013年]。正如在[34]中所观察到的，[4，41]的量子设置工作意味着任何大小为o（（n/log（1/log））2）的德摩根公式与n位奇偶校验的相关性最多为1/2+1/2。这与我们的傅立叶浓度结果（推论VII.1）所暗示的衰减界限论文的其余部分：我们在第二节中陈述了基础知识，并展示了如何适应[36]第三节在第四节中，我们证明了一般公式和只读德摩根公式所需的集中收缩结果。我们在第五节中导出了一般德摩根公式的傅立叶浓度结果，在第六节中导出了只读公式的傅立叶浓度结果。在第七节中，我们给出了傅立叶浓度结果的应用程序的相关奇偶校验，学习，压缩，和平均灵敏度的德摩根公式。我们在第八节中提出了一些悬而未决的问题(Some由于篇幅所限，本会议版省略了校样。本文的完整版本请参见[22]。II. 预防措施A. 符号我们用[n]表示集合1，2，.。. . ，n. 我们使用exp（a）来表示指数函数2a，其中a是某个2012年2月Σ∗·∈{}∈∈{}A1 n联系我们{}→ {−}{−}−Σ||∗i=1Σi=1Q数值表达式除非另有明确说明，否则所有的十进制数都是以2为基数的。B. 公式一个关于n个变量x1，. . .，xn二叉树是一个二叉树，其叶子由变量或其否定标记，其内部节点由逻辑 运 算 AND 或 OR 标 记 。 公 式 F 的 大 小 ， 记 为 L（F），是树中叶子的数量。一个德摩根公式被称为只读一次，如果每个每个Xi在0.. s和Exp[X] 1。则Pr[X >8 E]2−E/s。III.通过随机限制的更高浓度A. 出发点我们使用[36]的结果定理III.1（[36]）. 对于任意n元布尔函数f，整数t>0和实数0< p<1使得pt> 8，变量在树中最多出现一次。请注意，n个变量的只读公式的大小最多为n。Σˆ2Σˆ2C. 傅里叶变换|>t|>tf（A）≤2·Expρ∈Rp<$乙：|B|>pt/2f ρ（B）我们回顾了布尔函数的傅立叶分析的一些基础知识（参见，例如，[54]一项调查。我们认为一个n变量布尔函数是1，1-值的，即，如f：0，1n1，1。对于子集A[n]，我们用χ表示布尔函数映射x，. . .得双曲余切值.0，1n的奇偶性（1）i∈Axi。设f：0，1nR为任意函数. f在A处的傅立叶系数定义为：f∈（A）：=Expx0，1n[f（x）×A（x）]. 注意，f（A）是这就是f在计算χ A时的优势，χ A是来自A的输入的奇偶性。Parseval恒等式是A<$[n]f<$（A）2=Expx∈{0，1}n[f（x）2]. 注意对于布尔函数f：{0，1} → {−1，1}，我们得到A<$[n]f（A）= 1。D. 随机限制对于0< p<1，我们定义了n个变量的集合x1，. . .，xn如下：对于每个i[n]，以概率p为xi分配值（即，不限制x i），否则随机均匀地为x i分配值0或1。我们用RP表示p-限制类.对于布尔函数f（x1，. . .，xn）和一个随机限制ρ，f ρ表示使用ρ从f得到的限制函数; f ρ是不受ρ限制的变量的函数。对于布尔函数f，变量的子集S和字符串r∈ {0，1} |S|，符号fS←r表示f的限制，其中变量S被赋予r中给出的值。我们可以结合不同的限制。例如，fS←r，ρ表示f的限制，其中我们将值r赋给S中的变量，然后将限制ρ应用于变量[n]\S中的结果函数。E. 赫夫丁界限我们将使用以下版本的B-Hoeffding界限[11，21]。引理II.1（Hoff-Hoeffding）. 设X =tX i是独立随机变量的和，B. 德摩根公式想象一下，我们有一个0 tF（A）2≤2·γ。由于tn和p>1/n，这也迫使SN2/2。对于s≤n2−2，我们可以设置p=n<$/n，得到t=n1−<$。(Note既然我们需要pt> 8，我们得到p> t（1/s），因此t> t（s）。实际上，我们年龄首先，这是不正确的，因为公式可能有因此，我们需要确保重变量总是受限制的。其次，[24，34]中最著名的集中收缩结果对于非常小的p不起作用。绕过它的方法是一个接一个地应用许多随机限制，对于适当选择的p1，p2，.. . .，p k，从而模拟具有参数p =kpi的单个限制;这样的解决方法[24]和[34]中已经使用下面的引理将处理重变量。直觉上，它说，每个变量限制增加有效程度的傅立叶系数可以大到最多1。引理III.2. 设f是布尔函数，x是f的变量。 设f为f，x为0，f1为x- -| | ≥≤0A，|一|≥tΣΣ≥Σ.√≤ρ∈L（ Fρ）>2b· pΓ·n≤exp（−exp（n<$/2）），√i=1否则ρ′（x）= π。到1.对于任意δ>0，如果f∈（A）2 δ和一、|一|≥tf<$1（A）2≤δ，则A，|一|≥t+1f（A）2≤δ。证明：对于y：= 1 − 2x，我们可以写f =1/2（1 +y）f0+ 1/2（1y）f1= 1/2（f0+f1）+（1/2）（f0f1）y。然后，对于任何不包含x的集合A，f<$（A）2+f<$（x<$A）2=（1/2（f<$0（A）+f<$1（A）2+（1/2（f<$0（A）−f<$1（A）））2=1/2·f<$0（A）2+ 1/2·f<$1（A）2。用A对所有A求和t产量最多δ的约束函数的假设每个大小为t+ 1的B（包含x或不包含x）都包含在这个和中。收缩在每个批次中发生的概率很高，因此，对于整个原始配方也是如此。我们在下面提供更多细节首先，在第IV-A节中，我们给出了证明这两个结果的共同论据。然后我们证明了第IV-B节中的定理IV.1和第IV-C节中的定理IV.2A. 初步论点我们将使用以下“收缩预期”结果。HaBastad[18]表明，德摩根公式的收缩指数为2（另见[47]的替代，更严格的证明）。定理 IV.3 （[18]）。 存在一个C > 0这样因此，为了上界集合A的系数的傅立叶质量，|一|> t，这个想法是设置所有“重 ”对任意n元de Morgan公式F，对任意0p1，Expρ∈Rp[L（Fρ）]≤<<变量（比如说，其中的z）和傅立叶上界每个约束函数在集合B的系数上的质量，|B|>t-z。如果我们能把c·p2·μ（p，L（F））·L（F）+p·L（F）μ（ p，L（ F））= 1 +log3/2min{1/p，L（ F）}。得双曲余切值.每个限制函数的傅立叶质量乘以某个δ，那么，通过引理III.2，我们得到了原函数在大于（t-z）+z=t的集合上的傅里叶质量的相同上界。IV. C偏心 收缩 的 DEM ORGANHaBastad、Razborov和Yao[20]确定了只读公式的收缩指数; Dubiner和Zwick [12]收紧了他们的结果。定理IV.4（[20，12]）. 对于每个只读公式F（ x1，.. . ，xn）和参数0p1，公式在这里，我们证明了以下收缩结果，Expρ∈Rp[L（Fρ）]≤O.pΓ·n+p·n1/Γπ，通用和只读德摩根公式，隐含在[24]第10段。定理IV.1（一般德摩根公式的收缩）. 存在一个c >0，使得对每个L和每个de Morgan公式F，其中L（F）L对 n个变量，没有任何变量出现超过h次，并且对于每个0< p<1，其中，r = 1/log（5 − 1）3。27岁。接下来，我们分解一个给定的（通用或只读）德摩根公式如下。引理IV.5（[24]）. 对于任何正的s和任何德摩根公式F 在集合X上 变量当L（ F）> s时，存在m个de Morgan公式Prρ∈RpL（F）>cp2log3/2（1/p）L≤L（F）·2−p6L/h。G1，. . . ，Gm，其中m≤ O（L（F）/s），使得1) L（ Gi）≤ s，对于所有1≤i≤ m，定理IV.2（一次读取的德摩根公式的收缩）。对于任何一次读取的德摩根公式F（x1，. . .，xn）和p=（n <$/n）1/Γ，对于某个<$[0，1]，我们有2) 对于每个1≤i≤m，Gi在 X之外最多有2个“特殊”变量（不同的G i有不同的变量），并且3) 对于变量X的任何限制ρ， L（ Fρ）≤Σ ΣΣmL（（Gi）ρ'），其中ρ'（x）=ρ（x），x∈X（2）对于一个整数n=0（1/2），其中n = 0（3 .第三章。27岁。5−1）此外，如果F是一个只读公式，那么每个公式Gi在集合中。这两个结果都是使用相应类别的公式[18，20，12]的众所周知的“期望收缩”结果来证明的证明的思想是将一个给定的公式分解成几批独立的子公式（带有一些额外的条件），并对每个子公式应用“期望收缩”。由于每个批次中的子公式是独立的，因此我们可以使用Adriff-Hoeffding不等式来论证Prρ∈Rp证明草图：找到一个大小在s/2和s之间的子公式;一个大小最多为s的极大子公式的大小至少为s/2。将子公式替换为新变量，称为子树变量。重复查找具有2个子树变量且大小小于s的子公式，或具有至多1个子树变量且大小介于s/2和s之间的子公式。(Take一个最小的子公式，其大小大于s/2。如果它有更多−Σ··ρ我ρiρi ρ如果子树变量多于2个，则取至少有2个这样的变量的最小子公式;由于它的每个子公式最多有1个子树变量，所以它必须正好有2个。是对G′i的所有变量的p-限制，它与对Gi的所有变量的ρ′一致。我们有以下内容。因为每次，我们要么删除s个节点，最多1个新的子树变量，或减少数量索赔四.7. Exp[L（（Gi）ρ'）]≤2·Exp[L（（G'）ρ）].将公式划分为O（L（F）/s）个子公式，每个子公式的大小不超过s，子树变量不超过2特殊变量对应于作为其他一些子公式的输出的输入。我们想用引理IV.5第（3）项的上界来分析随机约束对F为此目的，我们需要处理一些随机的限制，指定变量（在我们的例子中是“特殊”变量）不受限制。其思想是取每个子公式Gi，并通过将Gi中的每个特殊变量替换为抗限制公式（在新变量上，对于不同的特殊变量不同）来构造新的子公式G′i仍然是一个非常数函数。然后，我们用标准随机约束ρ的期望大小Expρ[L（（G′i）ρ）]的两倍上界期望大小Expρ'[L（（G ′i）ρ'）]，对不受限制的特殊变量ρ'.后一个期望可以使用上述对于一般的德摩根公式，k个输入上的奇偶函数对于大多数p -限制不可能简化为常数函数，其中pk时间复杂度为O（k2）。对于一次读取的德摩根公式，从Valiant [50]的工作中得出了引理IV.6（[24]）. 对于每个

（1/2）·L（（G ′））。在这个不等式的两边取ρ′上的期望值，就得到了我们想要的结果。现在我们准备好证明我们的浓缩收缩效果了.B. 定理IV.1设s=c0p−2，其中c0为常数。 使用引理IV.5，将给定的公式F分解为O（L（F）/s）个子公式Gi设H是关于2/p个新变量的德摩根公式，用于计算奇偶校验函数。每一个这样的德摩根公式的奇偶校验2/p变量的大小为O（1/p2）。2/p个变量中的每一个被随机p-限制赋值（0或1）的概率为（1p）2/p≤e−2≤1/4。因此，H是抗收缩的。通过用公式H的独立副本替换Gi中的特殊变量来形成G′i。因为每个Gi是的大小至多为s=c0/p2，且H的大小为O（1/p2），则对某个常数c ′ 0，每个G′i的大小为c′0/p2. 通过权利要求IV.7和HavenstadExp[L（（Gi）ρ'）]≤2Expρ[L（（G′i）ρ）]≤c1log3/2s，（二）对常数c1，其中ρ′是对除特殊变量外的Gi的变量的p-限制，ρ是将ρ′推广到G′i的所有变量的p-限制.因此，我们有一个O（L（F）/s）公式的集合G i，每个G i的大小至多为s，使得G j中的h个以上没有变量出现，并且使得L（F ρ）≤ L（（Gi）ρ '）.因此，我们的引理减少到显示集中的随机变量，其期望值的上限由方程。（二）、因为每个Gi最多与 对于Gj由等式(2)因此，每个批 次 内 的 预 期 总 公 式 大 小 为 O （ L （ F ）（log3/2s）/（s2h））。作为一个随机变量，这是独立随机变量的总和，ρ'3/ 23··- -·Q−- ·−····−··{}→ {−}.ΣΣΣk≥0- 我. ..--∈范围0到s。根据引理II.1的Bauff-Hoeffding界，任何批次中公式大小之和大于c3L（F）（log3/2s）/（s2h）的概率小于2−k（L（F）（logs）/sh）。有严格的i限制应用于F，且令si为我们有F0=F和s0=n。考虑阶段i，其中1≤i≤k。如果si−1≤pΓn=n，则si也将以概率1小于n。小于L（F） ≤L批处理，因此一个联合绑定给 的 概率 的 所有 批次 是 身型限重O（L（F）（log3/2s）/（s2h）），除了概率Lexp（n（L（F）/（s3h）=Lexp（n（p6L（F）/h））。如果是，则对至多O（sh）批求和，L（Fρ）≤O（L（F）（log3/2s）/s）=O（p2L（F）log3/2（1/p））。C. 定理IV.2首先，我们证明了一个收缩的结果，适用于相对较大的参数p。定理IV.8. 存在常数d，d′>0，使得以下对于任何一次读取的de Morgan成立公式F（ x1，.. . ，xn）和0p1：假设si-1>n，我们通过定理IV.8得到：Prρ∈R[s i>dqΓ1 -2 - 3 - 4 - 5- d′Q8n≤实验的） d′n/2）。 因此，至少1k exp（d′n <$/2），则如所主张的，我们有s k≤dkq krn≤dkprn。V. DeMOrgan公式的傅里叶浓度本节的主要结果如下。定理V.1. 令f：0，1 n1，1是由德摩根公式F（x1，. . . ，xn）的大小最多为s。然后，对于任何常数0< <<$1/2和任何足够大的s，Prρ∈Rp ≤exp（−d′·p8·n），λfλ（A）2≤exp.-s/3。其中，r =1/log（5−1）3。27岁。证明：设置s=c/p4，为常数c被确定. 使用引理IV. 5，将给定的公式F（大小为n）划分为O（n/s）个子公式G1，. . .，G m的大小至多为s。设H是来自引理IV.6的抗收缩只读公式。定义G′i为Gi，其中Gi中的特殊变量替换为H的独立副本。|>s 1 / 2+ е|>s1/2+ еA. 主要结果定理V.1由下面的定量版本（通过将定理V.1的k/2与定理V.2的k /2定理V.2. 对于每个整数k>0，都有一个常数b，因此，对于任何计算的布尔函数f，根据德摩根公式，尺寸最大为s，对于注意，L（G′i）≤L（Gi）+O（1/p4），这可以是通过选择p>（c/L（G））1/4，使其最多为2·L（Gi）k=（11/12）k和t=s（1+k）/2，对于足够大的常数c >0。通过权利要求IV.7和定理IV.4，我们得到对于每个Gi，|>t|>tf（A）2≤ks·exp.−Ωs/4、日志bs经验ρ'[L（（Gi）ρ'）]≤c′·pΓ·s，（3）对常数c′，其中ρ′是Gi中除特殊变量外的变量的p-限制由引理IV.5，我们有L（Fρ）≤iL（（Gi）ρ'）.请注意，后者是独立随机变量的总和，因为不同的Gi中common（由于F是只读的）。这些随机变量中的每一个都在0. s，期望上限由等式（三）、因此，这些随机变量的和至多为c"npΓ，对于某个常数c"。以《易经》为题，引理II.1，L（Fρ）大于s足够大。证明：证明是通过对k的归纳。基本情况k= 0是平凡的，因为公式最多依赖于s个变量，并且求和是在大于s的集合上进行的。假设定理对。我们将证明k+ 1。令t=s（1+k+1）/2。设h=s。最多存在大于h-重（即，在最小公式中出现次数超过h次）对于f.设f′是f给重变量赋值的任何限制我们将证明每个f′都有8c“”npΓ小于2−c“"npΓ/s≤exp（d”p8n），对于某个常数d“。现在我们证明定理IV.2，通过递归地应用|≥t'|≥t'（A）2≤ks·exp.−s（定理IV.8.定理IV.2的证明：设q：=n−k/16，且k：= 16（1）/（r）。我们将对原始公式F应用k个随机q-限制。设Fi为公式F，其中t′=t/2。这个主张将由引理III.2推出，因为当s >4（12/11）k时，t > t′+s。对于每个这样的f′，考虑一个随机限制ρRp对于p=s−1/24/（c（logs）a），对于常数a和c，- -−[2014-05-23]···−.ρ{}→{−}Σ||γ⊆||·sk+1/4/polylogs- -γ..ΣΣΣ·√··−以后再选择根据定理III.1，我们得到ρ引理V.3. 对于任意γ> 0且t ≤ n，存在在n个 输入的大小为O（t2/nγ）的情况下，γA：|一|≥t'f′（A）2≤2·Expρ乙：|B组|≥pt'/2f′（B）2.计算t位的奇偶校验，优势为2−n。证明：考虑以下公式通过 定理 四.1、 除了 与 概率sexp（p6s/h）=s exp（n（s1/4/log6as）），函数方 程 fρ′ 的 公 式 大 小 至 多 为 s′′=c1p2slo g3/2s=（ c1/c2 ） s11/12 （ logs ） 3/2−2a=s11/12 （ logs ）3/2−2a，其中我们设置c：=c1。设t′′为定理与k和公式大小s"“，即，t′′=（s ′′）（1+k）/2F（x1，. . .，xn）。 集合m=nγ。 不失一般性假设m是奇数;否则取m 1 .一、除以x1，. . .，Xt分成m个不相交的块，每个块的大小为t/m 。使用大小为O （ t 2 /m 2 ）的deMorgan公式计算每个块的奇偶校验，并输出所有 块 上 结 果 的 AND 。 F 的 总 公 式 大 小 为 O（（t2/m2）m）=O（t2/m）。其次，我们认为F在com中具有优势2−m假设x的奇偶性，. . .，x.注意，F是正确的。1t=s（11/ 24）（1+k）·（logs）（3/4−a）（1+k）=s 11/24 + k+1/2·（log s）（3/4−a）（1 +k）。我们声称我们可以选择a使得pt′/2（定理III.1中的关键值）大于t′′。第一、pt ′/2 = s（1+k+1）/2 ·s−1/24/（4c（log s）a）当所有m个块都具有奇奇偶校验时，概率2-m如果不是所有的块都有奇校验，我们的公式总是输出0，这对于1/2的输入是正确的。根据引理V.3 ，由大小为s的函数f 可以具有f（A）>2−n，A的大小|A.|≤t，其中t满足O（t2/nγ）=s，=s11/24+logk+1/2/（4c（logs）a）=（t ′′/4c）（log s）a k−（3/4）（1+ k）。KK也就是说，0=0（实现Sn γ/2）。 因此，为了f<$（A）22−nе/6，需要设置<对于任何a >（3/4）（1 +n）/n，logs的指数t>|>t|>ts·n/12.将大于零，因此整个表达式将对于足够大的s，t′ ′大于t′′。因此，除了s exp（s1/4/log6as）分数之外，在收缩VI. 弗里尔 浓度 的 READ-ONCE DEM ORGAN公式本节的主要结果如下。（B）2≤ks′′ ·exp .−Ω（s′′）k/4多边形对数s′′定理VI.1. 设F（x1，. . .，xn）是任何一次读取德摩根公式计算布尔函数f：乙：|B|≥pt'/2..ΣΣ{0，1}n→n{1，−1}。那么，对于每一个001年，≤ks·exp−εSk+1/4.聚对数>logn），Σf∈（A）2≤exp（−n<$/3），由于傅立叶系数的平方和以1为界（通过Parsevalexp −Ω哪里|>n 1 /r + e|>n1/Γ+ еr= 1/log（5 − 1）3。27岁。p=（ n/n）1/Γ，由定理IV.2B. 傅立叶浓度的最优性，Gan公式设f：0，1n1，1是由大小为s的德摩根公式计算的布尔函数。由于m位的奇偶校验可以通过大小O（m2）计算de Morgan公式，我们有atf（A）=1，对于除γ以外的所有 ：=exp（ p -的n（n <$/2））分数限制将公式F 缩小到最多2bnn，对于某些b=O（1/n）。设t为2bnn=pt/2。我们得到t=n1/Γ+n（1 -1/Γ）2O （ 1/n ）≤n1/Γ+n，对于n ≥ n，2O （1/n ）≤n nn/3，这对n ≥ n（1/n）成立。 logn）。根据定理III.1，我们得出结论：|>t f（A）2 ≤|>tfˆ(A)2≤A[n]的大小 一 =O（k）. 因而为了得到傅里叶谱的一个非平凡的上界A>tf（A）2，我们需要设置t> s。事实上，正如我们将要讨论的，为了得到上界2−n，对于某些γ >0，我们需要设置t>snγ/2。这表明，我们的傅立叶浓度为次二次规模的德摩根公式，定理V.1，是紧的，直到参数前的常数因子。·，根据需要。证明：对于ΣΣ2γ≤exp（ 10）（n =2）≤exp（ n/3），根据需要。定理VI.1中的界限接近于最优（参见注七.6）。VII. A.申请A. 与奇偶校验的次二次型大小的de Morgan公式与奇偶函数有指数小的相关性−⊆≈−ǁ − ǁ{}→{−}−≈−联系我们/联系我们{−}∈{}| |·通过估计所有傅立叶系数f（A），推论七.1. 每一个大小不超过s=n2−2的德摩根公式，对于某个<0<1/2，都与n比特的奇偶校验函数在至多1/2 +exp（s/3）部分输入上一致。证明：回想一下，子集S [ n ]的傅立叶系数f∈（S）测量f与S中位置上的奇偶函数的相关性。这个结果直接由定理V.1得出。根据引理V.3，这个相关性界限本质上是最优的。B. 学习与[36]中一样，傅立叶浓度结果产生了一个布尔函数f的学习算法，可以通过小德摩根公式计算 ， 其 中 学 习 器 被 给 定 标 记 的 示 例 （ x ， f（x）），用于输入x上的均匀分布。学习算法产生一个函数g，使得g在几乎所有输入上都与fX.学习算法的误差（即，g和f不一致的输入部分）及其运行时间取决于相应计算模型的定理VII.2. 在均匀分布下，人们可以学习，在误差exp（ n（））对于任何0

下载后可阅读完整内容，剩余1页未读，立即下载