最难的半空间：多项式和有理逼近下界匹配平凡的上界实现所有半空间的最困难的问题

{}→{}最难的半空间Alexander A. 谢尔斯托夫ABS tRAC t. 我们研究半空间h的近似： 0、1个n0，1在无穷范数的多项式和有理函数的任何给定的程度。我们的主要结果是一个明确的建设“最难”的半空间，我们证明多项式和有理逼近下界匹配平凡的上界实现所有半空间。 这完成了一个漫长的 Myhill和Kautz（1961）开始的工作作为一个应用，我们构造了一个通信问题，它在符号秩和差异之间实现了最大可能的分离，O（n）对2−n（n）。等价地，我们的问题在具有无界误差和弱无界误差的通信复杂度之间表现出logn与log（n）的差距，在以前的构造上进行了二次改进，并完成了Babai，Frankl和Simon（FOCS 1986）开始的一系列工作我们的结果进一步推广到k-party number-on-the-forgem模型，在那里我们得到了一个显式的分离logn与n（n/4n）的通信与无界与弱无界误差。这个差距是对以前工作的二次改进，并且与前额上的数字下限的最新技术水平相匹配。计算机科学系，加州大学洛杉矶分校，洛杉矶，CA 90095。 sherstov@cs.ucla.edu网站由NSF CAREER奖CCF-1149018和Alfred P. Sloan基金会研究奖学金支持。arXiv：1902.01765v1 [cs.CC] 2019年2冠天慈1.介绍31.1. 最硬的半空间. . . . . . . . . . . . . . . . . . . . . . . . . .31.2. 谨慎与符号秩 . . . . . . . . . . . . . . . . . . . . . . . .41.3. 计算学习。. . . . . . . . . . . . . . . . . . . . . . . .71.4. 证据概述。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .82.第10章2.1.符号102.2.数论基础122.3.矩阵分析132.4.多项式近似162.5.有理近似172.6.符号表示182.7.对称化192.8.通信复杂性202.9.谨慎212.10.模式矩阵法223.整数集的离散性3.1.基本属性243.2.潜在界限243.3.一个明确的结构274.单变量化304.1.模m ~（31）线性型的分布4.2.Foolingdistributions324.3.单变量减少364.4.主定理405.主要成果415.1.多项式近似415.2.有理近似425.3.阈值43度5.4.阈值密度445.5.通信复杂性455.6.循环膨胀器47致谢49参考文献49附录A.Ajtai et al.53A.1.Shorthandnotation速记法54A.2.S的元素是非零且相异的54A.3.ksmall55的相关性A.4.klarge58的相关性A.5.第59章证据附录B.事实4.1的另一种证明p- 你好{}→ {−}{}→ {−}i=112−−1. 介绍用实多项式表示布尔函数在理论计算机科学中起着核心作用。逼近布尔函数f：0， 1n 1， +1的概念 逐点地通过给定次数的多项式的方法已经特别富有成效。形式上，令E（f，d）表示f通过次数至多为d的实多项式的无穷范数逼近中的最小误差：E（f，d）= min {<$f − p <$∞：deg p ≤ d}。对于任何函数f：0， 1n1， +1，这个量显然在0和1之间更详细地说，我们有0=E（f，n）≤E（f，n1）≤ ≤E（f，0）≤1，其中第一个等式成立，因为任何这样的f都可以用一个至多n次的多项式精确表示。布尔函数的多项式逼近的研究可以追溯到20世纪60年代Myhill和Kautz [59]以及Minsky和Papert [57]的开创性工作。 这一研究领域在过去几十年中发展迅速，与理论计算机科学中的其他学科有许多联系多项式逼近的下界有复杂性理论的应用，而上界则是算法设计中的一个工具.在前一类中，多项式近似使得电路复杂性[17，10，48，49，73，15]，量子查询复杂性[13，1，7，23]，和通信复杂性[20，65，22，73，75，66，52，26，70，15，79，78]。在算法方面，多项式逼近是迄今为止在计算学习中获得的许多最强结果的基础[82，45，44，37，61，8]，差分私有数据发布[84，25]和一般算法设计[55，36，72]。1.1. 最硬的半空间Myhill和Kautz 也称为线性阈值函数，半空间是任何函数h：{0，1}n→{−1，+1}表示n表ash（x）=sgn（nzixi−θ），对于某些固定的实数z1，z2，. . . ，zn，θ. 这一研究领域的基本问题是：给定次数的p多项式能很好地近似半空间吗Muroga [58]的早期发现是上限E（h，1）≤1−nΘ（n）（1.1）对于n个变量中的每个半空间h换句话说，每个半空间都可以用线性多项式逐点逼近，误差刚好小于1的平凡界许多作者追求E（h，1）上的匹配下界，对于特定的半空间h，最终由Håstad [33]明确构造，匹配Muroga对于d>2的E（h，d）的研究被证明是具有挑战性的。很长一段时间以来，由于Beigel [ 16 ]，基本上唯一的结果是下界E（h，d）> 1 2 −Θ（n/d）+1，其中h是所谓的奇最大位半空间。Paturi [62]证明了不可比较下界E（h，Θ（n））>1/ 3，其中h是上的多数函数n比特。 很久以后，E（h，Θ（n））> 1 2 −Θ（n） 在[76]中获得一个明确的半空间。这种分裂的状态一直持续到问题-问题在[77]中得到了完全解决，证明了这样的半空间h的存在性4Alexander A. 谢尔斯托夫−×→ {−}∈×1.ΣΣE（h，d）> 1 2-Θ（n），其中d = 1，2，. . .，Θ（n）。这个结果显然是强大的，因为它基本上匹配Muroga的上限近似的线性多项式。 在[77]中的工作进一步确定了最小误差，记为R（h，d），这个h可以近似为一个d次的ratio- nal函数，表明这个量对h来说也和对任何半空间一样大。我们的主要技术贡献是用这些性质来构造半空间理论m 1.1。有一种算法，它以整数n>1作为输入，在n中运行时间多项式，并输出半空间hn：{0， 1}n→ {-1， +1}，其中E（hn，d）> 1 − 2 −n（n），d = 1，2，. . . ，[cn]R（hn，d）> 1 − 2 −n（n/d），d = 1，2，. . . ，[cn]其中c> 0是绝对常数。经典的符号函数近似的界意味着，对于任何d，定理1.1中的下界本质上是n个变量的任何半空间的最佳可能（详见5.1节和5.2节）。因此，从多项式和有理函数逼近的观点来看，定理1.1的构造是“最难”的定理1.1不是[77]中存在性证明的去随机化，顺便说一下，我们仍然无法去随机化。相反，它是基于一种新的、更简单的方法，在本节末尾详细介绍考虑到半空间在理论计算机科学中所起的作用，我们认为定理1.1回答了一个独立感兴趣的基本问题。此外，定理1.1在通信复杂性和计算学习中也有应用，我们现在讨论。1.2. 离散与符号等级。考虑随机通信的标准模型[50]，其特征在于玩家Alice和Bob以及布尔函数F：XY1，+1。在输入（x，y）XY上，Alice和Bob分别接收参数x和y。他们的目标是以最少的通信在任何给定的输入上计算F。为了达到这个目的，每个参与者都私下拥有无限的均匀随机比特，他或她可以用这些比特来决定在协议中的任何给定点发送什么消息。协议的代价是在最坏情况下，Alice和Bob交换的比特总数。F的随机错误通信复杂度，记为R（F），是计算F的协议的最小成本，该协议在每个输入上的错误概率最多为F我们在本文中的兴趣是在通信协议的错误概率接近随机猜测，1/2。有两种标准的方法来定义函数F的复杂度，这两种方法都受到图灵机的概率多项式时间的启发[31]：和UPP（F）= inf0≤≤<1/2R（F）PP（F）= inf0≤≤<1/2.R（F）+log21.一、2−ϵ最难的半空间5{} × {}→ {−}{} × {}→ {−}--{} ×{} →{− }和2/5前一个量由Paturi和Simon [63]引入，称为具有无界误差的F的通信复杂度，参考错误概率可以任意接近1/2的事实。后者的数量，建议Babai等人。[11]，包括取决于错误概率的附加惩罚项我们称PP（F）为具有弱无界错误的F的通信复杂度。 对于所有函数F：0， 1n0， 1n1，+1，有平凡界UPP（F）≤ PP（F）≤ n +2。 这两个复杂性度量在通信复杂性理论中产生了相应的复杂性类，定义在Babai等人的开创性论文中。 [11 ]第10段。 通常，UPP是通信问题Fn：0，1n0，1 n的族Fn ∞ n =1的一类1， +1其无限错误通信复杂度至多是n的多对数。 其对应物PP类似地定义为复杂性度量PP。这两种大错误通信模型是两个中心的同义词，通信复杂性中的概念：符号秩和差异，在2.8和2.9节中正式定义。更详细地说，Paturi和Simon [63]证明了任何具有无界误差的问题的通信复杂度都可以通过其通信矩阵[ F（x，y）] x，y的符号秩来表征为一个加性常数。类似地，Klauck [40，41]证明了任何具有弱无界误差的问题F：0， 1n 0， 1n 1，+1的通信复杂性本质上是用F的差异来表征的。离散性和符号秩在通信复杂性之外享有丰富的数学生命[54，71，74，56]，这进一步激发了PP和UPP作为基本复杂性类的研究。根据定义，具有弱无界误差的通信并不比无界误差通信更强大，并且在Babai等人的论文发表20年后[11]不知道这种遏制是否适当。Buhrman等人[22]而作者[71]对这一问题的回答是肯定的，是独立的，并使用了不相关的技术。 这些论文展示了函数F：{0， 1}n×{ 0， 1}n→{−1， +1}，通信复杂度与非boundederrorversusweaklyunboundederror：UPP（Boundf）=O（logn）inbothworks，与[22]中PP（F）= n（n1/3）和[71]中PP（F）= n（n）相比 在复杂性方面-理论符号，这些结果表明，PP的UPP。Buhrman等人[ 22 ]的结果的一个更简单的替代证明在[75]中使用模式矩阵方法给出。最近，Thaler [83]展示了另一个非常简单的通信问题F：{0，1}n ×{0，1}n → {− 1，+1}，通信复杂度为UPP（F）= O（log n）PP（F）= N（n/log n）。总之，通信复杂性在我们的工作之前，无界与弱无界误差的区别是O（logn）与O（logn）的分离。的存在时间复杂度为O（log n），时间复杂度为O（logn），这是他在[77]中的工作这种情况与通信复杂性中的其他情况相似，例如多方通信中的P与BPP问题[14]，其中最佳存在分离比最佳显式分离强得多。有相当大的兴趣在通信复杂性的显式分离，因为他们提供了一个更深入和更完整的理解的复杂性类，而缺乏一个强大的显式分离表明我们的知识的基本差距。作为定理1.1的应用，我们得到：6Alexander A. 谢尔斯托夫{} ×{} →{− }n{}→ {−}n4K4K理论值m1.2。存在通信问题Fn： 0， 1n0， 1n1， +1，定义Fn（x，y）= sgn.w0+i=1我爱你（一、二）对于某些显式给定的实数w0，w1，. . .，wn，使得UPP（Fn）≤logn+O（1），PP（Fn）= N（n）.此外，委员会认为，rk ±（Fn）≤n +1，disc（Fn）=2 −k（n）。定理1.2本质上给出了通信类PP和UPP的可能的最强分离，在以前的构造上进行了二次改进，并与以前的非构造性分离相匹配。定理的另一个引人注目的方面是所讨论的通信问题的简单形式（1.2）。定理1.2中的最后两个界表明Fn的符号秩至多为n+1，偏差为2−n（n），这是最强的可能分离性。最好的以前的构造[71]实现了符号秩O（n）和差异2−n（n）。我们进一步将定理1.2推广到额上数k方模型，这是多方通信的标准形式类似于两方通信，k方模型有自己的类UPPk和PPk的问题，可有效地解决协议与无界错误和弱无界错误，分别。它们的正式定义见2.8节。在这种情况下，我们证明：理论值m 1.3。 存在k方通信问题Fn：（0，1n）k1，+1，定义Fn（x1，x2，. . . ，x，k）= sgn.w0+i=1wix1，ix2，i· · ·xk，i对于某些显式给定的实数w0，w1，. . .，wn，使得UPP（Fn）≤logn+O（1），PP（Fn圆盘（Fn）= 0。 现在，）=exp.-是的 不客气。定理1.3本质上给出了k方通信复杂度类UPPk和PPk的最强可能的显式分离，其中k≤（0. 5−10）logn最难的半空间7±±{}→ {−}. - 是的- 是的Σ0∧1D其中，k>0是任意常数。前一个最好的显式分离-这些类中的[27，80]是二次弱的，对于无界误差具有通信复杂度为n（n/ 4k），对于弱无界误差具有O（logn）定理1.3中的通信下限反映了通信系统中的现有技术区域，因为任何显式通信问题的最强下界F：（{0， 1}n）k→ {−1， +1}到目前为止是<$（n/2k）由于Babai等人。[12]。1.3. 计算学习。给定函数f的符号表示多项式：0， 1n1， +1是任何实多项式p使得f（x）= sgn p（x）对于所有x。f的符号表示多项式的最小次数称为f的阈值次数，记为deg（f）。显然，0 ≤ deg（f）≤ n对于每个n个变量的布尔函数f。 读者可以进一步验证符号表示等价于逐点逼近，其误差严格小于但任意接近于1的平凡误差。从学习的角度来看，符号表示多项式是有吸引力的，因为它们直接导致有效的学习算法。实际上，阈值次数d的任何函数根据定义是N=n+n+· ··+n单项式的线性组合尺寸.因此，f可以在N中的时间多项式的任意分布下使用各种半空间学习算法学习PAC [86符号表示多项式的研究始于50年前Minsky和Papert的开创性专著[57]，他们研究了几个常见函数的阈值程度。从那时起，阈值度方法已经为众所周知的硬概念类产生了最快的已知PAC学习算法，包括DNF公式[45]和AND-OR树[8]。在这一系列成功的例子中，显然没有提到半空间相交的概念.虽然已知该学习问题的几个限制的解决方案[18，51，87，9，44，46，43]，但没有发现用于PAC学习甚至两个半空间的交集的算法在时间上快于2 Θ（n）。另一方面，已知的硬度结果仅适用于多项式多个半空间或适当的[19、3、47、39]。这种情况促使人们寻求确定两个半空间相交的阈值程度[57，61，42，76，77]。在我们工作之前，最好的下界是两个半空间的显式相交[76]，由紧但高度非构造性的下界补充[77]。利用定理1.1，我们证明：THEOREm使得1.4. 有一个（显式给定的）半空间hn：{0， 1}n→ {− 1， +1}deg ±（hn<$hn）= deg（n）。上面的符号hnhn代表两个hn在不相交的变量集上的交集。换句话说，定理1.4构造了两个半空间的一个显式交，其阈值度是渐近最大的，即n（n）。 虽然[77]中的非构造性下界已经排除了阈值度方法作为学习半空间相交的一种方法，但我们认为定理1.4为这个难题提供了一个关键的定性部分。具体地说，它构造了一个小而简单的两个半空间的交叉家庭，这是所有已知的限制8Alexander A. 谢尔斯托夫∧. Σ1{−}{−}{−}····{−}.算法方法（即，通过将hnhn应用于变量x1，x2，. . .，x4n）。1.4.证据概述。我们的解决方案有两个主要组成部分：一个稀疏的整数，出现随机模m的建设，和一个多元布尔函数的单变量化我们将详细描述每个组件整数集的离散性。 设m>2是一个给定的整数。 我们工作的关键是m-差异的概念，它量化了任何给定的整数多重集的伪随机性或模m的周期性。它在很大程度上与沟通复杂性差异的概念无关（第1.2节）。形式上，非空多重集Z ={z1，z2，. . .，zn}被定义为n圆盘（Z，m）=最大值k =1，2，...，m−1nωkzj. 、.j =1。其中ω是本原m次单位根。这个基本量出现在组合学和理论计算机科学中，例如，[30、69、2、38、64、5]。恒等式1 +ω+ω2++ ωm−1= 0对于任何m次单位根ω=1，集合Z = 0，1，2，. . .，m1实现最小可能的m-差异：disc（Z，m）= 0。使用概率方法可以证明存在许多具有较小m-偏差的稀疏集（事实3.3和推论3.4）。具体地说，对于任何常数λ> 0，人们很容易验证集合Z 0，1，2，...的存在性。. .，m1，m-差异最多为0，基数为O（log m），稀疏性与平凡集0，1，2，. . .，m 1。我们知道Ajtai等人[2]和Katz [38]提出的两种有效的m-偏差小的稀疏集构造方法。Ajtai等人的方法是基本的，除了上诉素数定理，而Katz的构造依赖于数论中的深刻结果。这两项工作似乎都没有直接暗示我们所需要的那种最佳去随机化，即一种算法，该算法在logm中的时间多项式中运行，并产生一个基数为O（logm）的多重集，m-差异远离1。我们得到这样一个算法，通过调整Ajtai等人的方法。[2]的文件。Ajtai et al.[2]作者称之为迭代引理，在本文中称为定理3.6。 它的作用是减少 对于素数p m，将m-偏差小的稀疏集的构造推广到p-偏差小的稀疏集的构造。Ajtai等人[2]证明了 他们的迭代引理为m素数，但我们表明，他们的论点容易generalizes到任意模m。通过以递归方式应用迭代引理，可以得到越来越小的素数。[ 2 ]的作者继续这个递归过程，直到他们达到素数p如此之小，以至于平凡结构0，1，2，. . .，p 1可以被认为是稀疏的。我们以不同的方式进行，并在两个阶段后终止递归，此时输入大小足够小，可以基于概率方法进行蛮力搜索我们构造的最后一组具有m的大小对数和m-差异是一个小常数，而不是Ajtai等人的工作中的超对数大小和o[2]的文件。我们注意到，这种修改后的方法还给出了第一个显式循环扩展的n个顶点的程度为O（logn），这是最佳的，并改善了最难的半空间9Σ−联系我们·Σ−联系我们···联系我们联系我们−--联系我们{}→ {−}考虑线性映射L：{0， 1}n→ Zm，由L（x）=联系我们zixi. 此时此刻联系我们（logn）O（logn）O（logn）的前最佳度界，由于Ajtai et al. [2]。循环扩张器的背景知识和扩张器构造的细节可以在5.6节中找到。单变量化 我们现在描述我们证明的第二个主要组成部分。 考虑半空间hn（x）=sgn（zixiθ）中布尔变量x1，x2，. . . .. 则线性形式zixiθ在离散集合1，2，. . .，N，对于与系数的幅度成比例的某个整数N。因此，可以通过将符号函数近似为1，2，. . .，N . 这种方法适用于有理逼近和多项式逼近。 我们把它看作是近似h n的黑盒方法，因为它使用线性形式zixiθ而不是单个位。没有理由期望黑盒结构接近最优。事实上，有半空间[76，第1.3节]，可以近似到任意小的误差由一个有理函数的次数为1，但需要一个黑盒近似的次数为n（n）。令人惊讶的是，我们能够构建一个半空间hn指数大系数的黑盒近似基本上是最佳的。 其结果是，紧下限的合理和多项式逼近的Hn紧接着从一元下界近似的符号函数 1，2，3，. . .、 2Θ（n）。 hn的作用是将这项工作中的多元问题简化为一个易于理解的单变量问题，因此术语单变量化。hn的构造涉及几个步骤。首先研究了加权和z1X1+z2X2++ znXn模m，其中z1，z2，. . . ，zn是给定的整数，并且位X1，X2，. . . ，Xn0，1是均匀随机选择的。 我们证明了当多重集{z1，z2，. . . ，Zn}具有远离1的m-偏差。对于下一个步骤，固定一个任意多个集合{z1，z2，. . . ，zn}，其中sm≠所有m-差异，并且证明，我们知道，对于均匀随机X0， 1n，概率分布-L（X）的分布指数地接近均匀分布。 这意味着，函数L−1（0），L−1（1），. . .，L−1（m 1）具有近似相同的傅立叶谱，直到次数cn，对于某个常数c> 0。 我们通过证明存在概率分布μ0，μ 1，.，μ 0，μ1，..，μ1，..，μ 1，.. ，μ 2，.，来大大加强这一结论。. . 、µm−1，支持L−1（0）、L−1（1）、. . .，L−1（m−1）的傅立叶谱，使得μ0，μ1，. . . ，µm−1在次数cn之前完全相同。我们的证明依赖于[77，定理4.1]中的一个通用工具，在那里使用Gershgorin圆定理证明。作为最后一步，我们使用µ0、µ1、. . . ，µm−1，以下列方式构造半空间：z1，z2，. . . ，zn，其有理函数和多项式的逼近给出了离散集1，2，. . .，m。更一般地，对于任何元组z1，z2，. . .，zn，我们定义了一个相关联的半空间，并证明了一个下界的多重集z1，z2，. . . ，zn. 结合这个结果和一个整数集的有效构造，当m= 2Θ（n）时，我们得到一个显式的半空间hn：0，1 n1，+1，其多项式和有理函数的逼近等价于符号函数在1，2，3，. . .，2 Θ（n）。Theo-rem1.1现在通过呼吁已知的多项式下限，10Alexander A. 谢尔斯托夫∧--↔ ↔ −↔↔-∈12222符号函数的有理逼近为了获得通信复杂度的指数分离，具有无界误差和弱无界误差（定理1.2），我们使用模式矩阵方法[73，75]将最后，我们关于两个半空间相交的阈值度的结果（定理1.4）通过将定理1.1的有理逼近下界与[76]中关于f f形式的任意函数的符号表示的结构结果相结合而起作用。本文的一个关键的技术贡献是识别的m-差异作为一个伪随机属性，是弱到足以承认有效的去随机化和强大到足以允许相应的半空间的单变量化[77]中先前的存在性结果使用了完全不同且更复杂的伪随机特性，该伪随机特性基于傅立叶变换在0， 1n上的仿射移位，我们无法对其进行去随机化。除了构造一个低差异集之外，我们的证明比[77]中的存在性证明更简单，更直观。2. PRELI mI naRIES我们首先回顾一下技术资料。这一部分的目的因此，专业读者应该略读这一节的注释，或者干脆跳过。2.1. 记法。对于布尔值有两种常见的算术编码：传统的编码false 0，true 1和傅立叶激励的编码false 1，true 1。在整个手稿中，我们使用前者的编码域的布尔函数和后者的范围。 按照这个约定，布尔函数是映射{0，1}n→ {−1，+1}，其中n是某个。对于布尔函数f：{0，1}n→ {−1，+1}和g：{0，1}m→ {−1，+1}，我们设fg表示f与g的坐标复合。形式上，fg：（{0，1}m）n→{-1， +1}由下式给出：（f ∈ g）（x，x，. . . 得双曲余切值.）= f. 1 − g（x1），1 − g（x2），. . . ，1 − g（xn）<$，（2.1）其中右手侧的线性映射用于在域与范围的不同算术化之间切换的目的。集合X上的部分函数f是其定义域（记为dom f）是X的非空真子集的函数。 我们将坐标复合f g以自然的方式推广到部分布尔函数f和g。具体地说，f g是由公式2.1给出的布尔函数，domain是所有输入的集合（. . . ，xi，. . . ）∈（dom g）n，其中（. . .，（1g（xi））/2，. . . ）domf.我们使用以下两个版本的sign函数：−1 ifx0，sgnx =0 ifx = 0，ifx>0，Sgnx=−1如果x<0，如果x> 0，则为1。.n最难的半空间11.Σ{}→ {−}.| |联系我们⊕ ∩∪→ǁ ǁ||∈- -→Kxi−2 −4对于子集X∈ R，我们令sgn |X表示符号函数的限制，X. 对于我们来说，半空间是任何布尔函数h：{0，1}n → {−1，+1}，由下式给出h（x）=sgnni=1wixi−θ对于一些实数w1，w2，. . . ，wn，θ. 多数函数MAJ n：0，1 n1，+1是定义为.卢恩n1i=1=−1如果x1+ x2+· ··+xn> n/2，1否则。一些作者只对n奇数定义MAJn，在这种情况下，决胜项为1/ 4可以省略。集合S的补集和幂集通常用S表示，P（S）。 集合S和T的对称差是ST =（ST）（ST）。在整个手稿中，我们使用大括号表示法，如z1，z2，. . .，zn指定多集合而不是集合。 基数 Z 有限多重集Z定义为Z中元素出现的总数，每个元素出现的次数与它出现的次数相同多重集上的相等和子集关系的定义类似，考虑到元素出现的次数例如，{1， 1， 2} ={ 1， 2， 1}，但{1，1， 2}=而是{1，1，2}<${1，2}。{1，2}。 类似地，{1， 2}{ 1， 1， 2}函数f：XR的无穷范数记为 f∞= supx Xf（x）.对于实值函数f和g及其定义域的非空有限子集X，我们写1Σf，g<$X=f（x）g（x）.|X|x∈X我们经常使用这个符号，X是f和g的域的非空真子集。 我们让ln x和log x分别代表x的自然对数和x以2为底的对数。二进制熵函数H：[0，1] [0，1]由H（p）=plog p（1 p）log（1 p）给出，并且在[0，1/2]上严格递增。下面的边界是众所周知的[35，p。283]：i=0 . n我 ≤2H（k/n）n，k = 0，1，2，. . . 、，n，2.（二、二）对于复数x，我们通常分别用Re（x）、Im（x）和x表示x我们用黑体字来表示虚单位i，以区别于索引变量i。对于任意整数a和正整数m，回想一下，a mod m表示{0，1，2，.. . . ，m-1}，其与模m全等。 为MAJn（x）=−sgn12Alexander A. 谢尔斯托夫--.Σ.Σ−{−}−≡ ≡ −≡≡.Xi−p>δ当整数m>2时，Zm和Zm分别表示模m整数环和模m整数乘法群对于多重集Z ={z1，z2，. . .，zn}，我们采用标准表示法−Z ={−z1，. . . ，−zn}，（2.3）aZ={az1，. . . ，azn}，（2.4）Z+ b ={z1+ b，. . . ，zn+ b}，（2.5）Zmod m ={z1mod m，. . . ，znmod m}。（二、六）注意，（2.3）-（2.6）中的多重集 我们经常将这些简写组合使用，如（aZ +b）mod m =（az1+ b）mod m。. .，（azn+ b）mod m .对于逻辑条件C，我们使用Iverson括号I[C]=1如果C成立，0否则。下面的浓度不等式，由于Hoeffding [34]，是众所周知的。公式2.1（Hoeffding不等式）。 设X1，X2，. . . ，Xn是独立的随机变量，其中Xi∈ [ai，bi]. 让np=E Xi.i=1然后- 是的你好Σi=1.2 δ2Σni=1-ai）2 （b）我在事实2.1和本文中，我们使用大写字母来表示随机变量。2.2. 数论的基本原理对于互质的正整数a和b，（a-1）b1，2，. . .，b1表示a模b的乘法逆。下面的事实是众所周知的，很容易核实; cf. [2]的文件。面2.2。 对于任何互质的正整数a和b，（a−1）b（b−1）a 1b+a−ab ∈ Z。（2.7）证据我们有a（a−1）b + b（b−1）ab（b−1）a1（mod a），类似地a（a−1）b + b（b−1）aa（a−1）b1（mod b）。因此，a（a−1）b+b（b−1）a1可以被a和b整除。 由于a和b是互质的，我们得出a（a−1）b+ b（b−1）a1可被ab整除，这等价于公式2.7。P≤2次暴露.最难的半空间13∼Σlnn××{−}d10···0回想一下，对于实参数x>0，素数计数函数π（x）的计算结果是小于或等于x的素数的个数。在下文中，从上下文将清楚π是否指3。14159 . . 或素数计数函数。后者的渐近增长由素数定理给出，该定理指出π（n）n/ln n。π（n）的许多显式界是已知的，例如Rosser[68]的以下定理。FACT2.3（Rosser）。 对于n>55，nlnn +2 <π（n） 1，根据定义有ν（n）个不同的素因子。让pk表示第k个素数，我们有lnn> ln p1p2. . . pν（n）ν（n）>ln（k+1）k=1>中文（简体）=ν（n）lnν（n）−ν（n）+1，其中第二步骤使用平凡估计pk>k + 1。在这个推导过程中，第二步是公式2.8，而最后一步是公式2.9。2.3. 矩阵分析。对于任意集合X，如X = C或X = 1，1，符号Xn×m表示元素在X中的n m矩阵族。符号In和Jn，m分别表示n阶单位矩阵和所有1的n m矩阵 当矩阵的维数从上下文中很清楚时，我们省略下标，简单地写I或J。. . .. . . ，dn在对角线上：diag（d1，d2，. . . ，dn）=0d2···0。- 是的.. . ..1lnx dx0 0···dn14Alexander A. 谢尔斯托夫Σ∈ǁǁ||ǁǁ||j=0拉吉ΣΣΣ=c（j-k+1）modmω（j-k+1）modmvk对于矩阵M=[Mi，j]，回想一下它的复共轭由M=[Mi，j]给出。M的转置和共轭转置分别记为MT和MT=MT。共轭、转置和共轭转置运算作为特殊情况应用于向量，我们将其视为具有单列的矩阵。我们使用熟悉的矩阵范数M∞=maxMij和M1=Mij。同样，这些定义作为一种特殊情况也适用于向量。一个矩阵MCn×n称为酉矩阵，如果MM=MM= I。一个循环矩阵是任何矩阵C∈ Cm×m的形式c0c1c2···cm−2cm−1cm−1c0c1···cm −3cm −2C=cm−2cm−1c0···cm−4cm−3.（2.10）.... . ..c2c3c4···c0c1c1c2c3···cm−1c0对于某个c0，c1，. . .，cm−1∈ C. 因此，C的每一行都是通过将前一行向右循环移位一个条目来获得的。设circ（c0，c1，. . .，cm−1）表示式（2.10）的右侧。在该符号中，circ（1，0，. . .，0）= I且circ（1，1，. . . ，1）= J. 循环矩阵的特征值和特征向量是众所周知的，并且很容易确定。为了方便读者，我们在事实2.5和推论2.6中包括了下面的简短推导。FACT2.5. 设C = circ（c0，c1，. . .，cm-1）是循环矩阵。 则对于每个单位ω的m次根，向量1ωω2.ωm−1（2.11）i是C的特征值ector，特征值em−1cjωj。证据 设v表示公式2.11中的向量。 则对于k = 1，2，3，. . . ，m，m−1（Cv）k=c（j-k+1）modmωj=0m−1=j=0mj=0c（j−k+1）modmωj−k+1vkm−1=j=0cjωjvk，最难的半空间15Σ ΣΣΣ拉克杰ΣΣ./ΣΣΣm·CW=W诊断j=0其中第三步使用ωm= 1。作为事实2.5的推论，我们可以求出任何循环矩阵C的特征值的全部补数，并且还可以知道C酉类似于对角矩阵。 在下面的陈述中，回想一下本原m次单位根是xm−1 ∈Q[x]的根的乘法群的任何生成元，例如exp（2πi/m）C OROLLAR y 2.6. 设C = circ（c0，c1，. . .，cm-1）是循环矩阵。设ω是本原m次单位根然后矩阵W=[ωjk/ωm]j，k=0，1，.，m−1是单一的，并且满足m−1WCW=诊断j=0cj，m−1j=0cjωj，m−1j=0cjω2j，. .. 、m−1j=0cjω（m−1）j。 （2.12）特别是，C的本征值，计数多重性，是m−1cjω，k= 0，1，2，. . . ，m−1。j=0证据 对于k，k′= 0，1，. . . ，m-1，我们有m−1 ωjkωjk'1m−1j（k−k'）j=0j=0=1个如果k=k′，0否则，其中第二步是可变的，因为ω是初始的，并且特别地ωk=ωk'。我们的结论是WW= WW = I.（二、十三）事实2.5意味着mj=0m−1cj， j=0m−1cjωj，j=0m−1根据式（2.13），它与式（2.12）等价。ωcjω2j，. .. 、cjω（m−1）j，16Alexander A. 谢尔斯托夫→pϵD2N·t+2-1近似于2.4. 多项式逼近。回想一下，多元实多项式p：Rn的总次数R，表示为deg p，是p的任何单项式的最大程度。我们在本文中互换使用术语“度”和“总度”。设f：X → R是定义域为X <$Rn的函数. 对于任何d> 0，定义E（f，d）=inf<$f−p<$∞，其中下确界是在次数至多为d的实多项式p上。 换句话说，E（f，d）是f的次多项式的逐点逼近中的最小误差。 不大于D。f的n阶近似次数是多项式p在n阶内逐点近似f的最小次数：f − p在这个概述中，我们专注于符号函数的多项式逼近。我们开始与一个近似由于Buhrman等人的基本建设。[21 ]第20段。因子T2.7（Buhrman等人）. 对于任何N >1和 0<<$1，符号函数可以在[−N，−1]<$ [1，N]上逐点逼近到<$以内，逼近次数为O.N2log 2μ m。事实2.7中的度上限并不严格。实际上，O（Nlog（2/n））的二次更强界以一种直接的方式从逼近论中的杰克逊定理[ 67，定理1.4]中得出我们的应用程序并没有从这种改进中受益，但是，我们选择Buhrman等人的建设[21]因为它的简单性。为了读者证明（改编自Buhrman等人）对于一个正整数d，考虑度-三维一元多项式Bd（t）=i=0）d/2¶. d我ti（1− t）d−i。换句话说，Bd（t）是观察到至少和尾巴一样多的正面的概率，d个独立的抛硬币序列，每个硬币正面朝上的概率为t。根据Hoeffding不等式（事实2.1），对于足够大的d = O（N 2 log（2 /n）），多项式B d发送[0，1 − 1 ] → [0，n]，类似地[ 1 + 1，1] → [1 − n，1]。 作为2 2N 2. 1212N2在[−N，−1]上逐点符号函数<$[1，N]在<$内。在下界方面，Paturi证明了低次多项式不能很好地近似多数函数。他实际上获得了类似的结果，所有对称职能，但特殊情况下，多数将足以满足我们的目的。结果，移位和缩放的多项式2Bd最难的半空间171联系我们- − −→- −→联系我们|[−1]nn.Σp（x）. MAJn（x）−sp21（−1）xj+1。N温度2.8（Paturi）。 对于某个常数c >0和所有整数n> 1，E（MAJ n，cn）>3。Paturi定理中的常数1/3可以用（0，1）中的任何其他常数代替。他的结果是我们感兴趣的，因为随着事实2.7，它意味着一个下界的符号函数的近似的离散集的点1，2，. . .、N为任何N。位置2.9。 对于所有正整数N和d，. d1/2证据缩写E=E（sgn {±1，±2，.，±N}，d），并且固定次数至多为d的多项式p，其近似1，2，.. . .，N内，事实2.7给出了一个O（1/（1<$）2）次多项式s，它发送[ 1<$，1+<$][ 4/3，2/3]和[1/3，1 + 1/3] [2/3，4/3]。那么这两个近似式的合成服从Maxt =±1，±2，.，±N|≤3。| ≤3 .这反过来又给出了