没有合适的资源?快使用搜索试试~ 我知道了~
1·几乎线性尺寸的达纳·莫什科维茨(DanaMoshkovitz)二○ ○六年十一月十九日摘要我们展示了一个PCP的建设与次常数误差和几乎线性的大小。具体地说,对于常数0 <α<1,我们构造了一个PCP验证器,用于检查布尔公式的可满足性,在输入大小为n的情况下,使用log n + O((log n)1−α)个随机位在由O((log n)1 − α)个位组成的符号上查询大小为n2 O((log n)1−α)的证明中的常数位置,并实现错误2−n((log n)α).通过曲线技术[1]的聚合的一个新的随机有效的版本的建设。它的主要成分是最近的低次检验,具有次常数误差和几乎线性尺寸[12],以及用于构建平衡曲线短列表的新方法。moshkovitz @weizmann.ac.il. 计算机科学与应用数学系,魏兹曼研究所,以色列.[10] ran. raz@weizmann.ac.il。魏茨曼大 学 计算机科学与应用数学系研究所,Rehocal,以色列。2∈∈∈∈∈NPNP--•∈NP21介绍证明的概念是计算机科学理论的基本兴趣一个定义为所有语言L的类,其中成员资格可以有效地证明。也就是说,有一个算法(称为验证器),给定输入x的大小为n,以及一个证明π的大小多项式在n中的陈述如果x/L,则对于任何声称的证明π,验证者拒绝。PCP定理[2,1](PCPfor Probabilistically Checkable Proofs)指出,所有语言Lin都有多项式大小的证明,可以通过仅查询证明中的常数位置来概率地验证 当PCP验证者可以访问输入x和证明π时,他会抛出r个硬币,用它们来选择q到π的常量查询,并满足以下条件:(i)如果x L,那么,和以前一样,存在一个验证者总是接受的证明π;而(ii)如果x/L,那么对于任何声称的证明π,验证者接受的概率最多为ε。ε项称为PCP的误差。PCP验证器的正式定义如下:定义1(PCP验证器)。一个PCP验证器,用于语言L,其大小为s:N→N,随机复杂度r:N→N,查询复杂度q:N→N,答案大小为a:N→N,完全完备,错误率ε:N→(0,1),是一个概率多项式时间图灵机,它给定对输入x∈ {0, 1}n的访问,以及对大小为s(n)的证明π的预言访问,证明π的大小为s(n)。从0, 1a(n)中选取符号,(i)投掷r(n)个随机硬币;(ii)在π中选取q(n)个索引;(iii)查询每个索引以获得长度为a(n)的相应答案;(iv)决定是否接受或拒绝;并满足以下性质:• 完备性:如果x ∈ L,则存在一个证明π,验证者总是接受它。可靠性:如果x/L,那么在访问任何证明π的情况下,验证者接受的概率至多为ε(n)。除了是一个关于证明能力的令人惊讶的结果之外,PCP定理与近似的难度有着紧密的联系这种联系使大量的结果表明,近似许多优化问题的各种因素是困难的。PCP定理和用于证明它的技术也激发和启发了许多有影响力的概念,如本地测试和本地解码。鉴于PCP定理的重要性,人们一直在进行长期的研究以试图改进它。1.1减少错误原始PCP定理[2,1]给出误差ε=1。 一个自然的目标是减少错误,最好是次常数误差O(1)。然而,验证者对证明进行q次查询,其中证明的每个符号是一个比特,其错误至少为2−q。因此,为了允许子常数错误,我们考虑每个符号由a位组成的证明,其中a是非常数。对于应用(例如,近似的困难[4]),很多时候甚至对数答案大小A(对应于多项式大小的字母表)也是允许的,而期望保持查询的数量Q恒定。3····这条道路的研究是在几个作品[4,14,3,9]。最先进的是[9],他构造了一个PCP验证器,对于任何常数0<α 1,该验证器在输入大小为n时使用O(logn)个随机位来查询n中的大小多项式证明中的一个常数位置,该证明最多由O((logn)α)个位组成,并实现了次常数误差2−k((logn)α)。1.2减小尺寸原始的PCP定理[2,1]给出了对于大常数c,输入大小nc的大小多项式的证明。一个自然的目标是减少大小,最好是在输入大小n1+o(1)中几乎线性。这条研究路径在诸如[13,11,7,6,5,8]的作品中被采用最先进的是Dinur [8],他构造了一个PCP验证器,用于检查大小为n的布尔公式的可满足性,其中具有几乎线性大小npolylogn,随机性logn+O(log logn),查询次数恒定,答案大小恒定和错误恒定。1.3次常值误差与近似线性尺寸是否存在亚常数误差和几乎线性尺寸的PCP的问题是公开的。在[12]中采取了这个方向的一个步骤,其中构造了次常数误差和几乎线性尺寸的低度检验 低阶检验是大多数PCP构造中的重要成分,并且[12]的构造似乎也应该产生具有次常数误差和几乎线性尺寸的PCP。这项工作证实了这一猜想。我们的主要定理如下。定理2(主). 存在一个常数0 <α<1,有一个PCP验证器用于检查布尔公式的可满足性,在输入大小为n的情况下,使用log n + O((log n)1−α)个随机位在由O((logn)1 −α)位组成的符号上查询大小为n 2 O((log n)1 −α)的证明中的7个位置。验证者具有完美完备性和误差2 −<$((log n)α)。我们注意到,通过我们的构造实现的误差和大小不如分别为每个参数已知的最佳误差和大小对于一个小的常数α,我们得到了n2O((logn)1−α),它确实是几乎线性的n1+o (1),然而,Dinur的构造[ 8 ]的大小对于某个小常数0<α 1,我们得到误差2−<$((logn)α),它确实是次常数o(1),然而,对于任何常数0<α 1,[9]的构造误差可以低至2−<$((logn)α)是否可以同时优化尺寸和误差这两个参数的问题仍然没有解决。1.4概述我们的构建包括三个概念步骤:1. 放大:这一步需要一个具有常数误差的PCP验证器,并产生一个具有次常数误差2−k((logn)α)的PCP验证器,但对证明进行非常数数量的查询O((logn)α2. 聚合:这一步需要一个PCP验证器,它对证明进行非恒定数量的查询O((log n)α),并产生一个PCP验证器,它只进行恒定数量的查询,但对一个答案大小为2(log n)O(α)的证明。4∈3. 减少答案大小:这一步将前一步中构造的PCP验证器的答案大小减少到O((logn)1−α)。放大步骤的输入是具有恒定误差的PCP验证器,其具有低随机性复杂度和几乎线性的大小,即, 它仅使用(1 + o(1))log n个随机比特来查询大小为n1+o(1)的证明。许多现有结构中的任何一种都可以用于此目的。我们使用Dinur的构造[8]。重要的一点是,我们以保持低随机性、复杂性和小尺寸的方式实现了这三个步骤。扩增步骤是标准的,并且在扩展器上使用随机游走聚合步骤是主要的新步骤,我们在下面讨论它 为了减少答案的大小,我们使用[14,9]中的思想来测试和读取低次多项式。值得注意的是,与先前的构造不同,该步骤在没有PCP验证器的递归组合的情况下完成。聚合来 聚集步骤是构造的主要新步骤,并且它是通过[1]的曲线聚集技术的新的随机有效版本来完成的。该技术假设PCP验证器V对大小为s的证明进行q次查询,并且构造新的PCP验证器VJ对具有大答案大小的稍微大的证明进行恒定数量的查询 让我们简要描述一下基本技术,以及以保持低随机性、复杂性和几乎线性大小的方式使用它的困难。对于足够大的有限域F和维数m,V的证明可以通过Fm中的低次多项式编码(其所谓的低次扩展)。 索引{1,. . . ,s}与F m中的点相同,并且在这些点上的多项式的求值给出了在相应的位置进行验证。VJ的有效证明π包含了对V在Fm中所有点上的证明的低次扩展的评估,以及它对Fm中某些子空间和曲线的限制。验证者VJ使用对证明的恒定数量的查询来模拟V,如下所示:1.我把硬币扔给V。 Suppose→x1,. . . ,→xqFm是对应于V在掷硬币的结果上查询的位置的任何一个的q p o i n t。2. VJ通过一个q次曲线vec,q为h→x1,. . . ,→xq和n ghapointt→xq+1c从Fm中随机一致地选取.VJ质疑证明曲线c的低次扩张的限制π(c)。这是一个多项式的次数最多q倍的程度低程度的扩展。3. V_J在曲线V_c上选择t→x的一致随机点,其中t→x不设为e→x1,. . . ,→xq. 本文用低次检验证明π(c)在→x上的取值与低次扩张是[Note如果π(c)在c上的许多点上与Fm上的低次多项式一致,则它在c上的所有点上与多项式一致,特别是在→x1,. . . ,→xq.]4. VJ使用π(c)在→x1,. . . ,→xq到V的近似值。验证者VJ只进行一个常数数量的查询:一个对π(c)的查询和一个常数数量的低度测试所需的查询这些查询是对一个答案大小很大的证明进行的:包含对子空间和曲线的限制。5∈∈ε2∈•→x,. . . ,→x→x∈F1 qq+1εΣ||∈VJ不是随机有效的,因为除了为V掷硬币之外,它还选择了另一个独立的均匀分布dpoint→xq+1如果我能穿过一条曲线。由此产生的证明大小至少是二次的,因为每次固定V的硬币投掷,它包含以下条目|曲线.|curves. [回忆一下,|Fm| ≥ s]。附加的均匀分布dp在t→xq+1上的原因FMIS要求DIST低程度测试仅在平均情况下工作良好。 为了具有低的错误概率,验证者应该在Fm(或接近于such)中均匀分布的点t → x上应用低度测试。当→xq+1是均匀分布的,它并不意味着曲线上的所有点都是均匀分布的,但设为e→x1,. . . ,→xq,在Fm中均匀分布。在不使用额外的独立均匀分布点的情况下,使ve→x在Fm中均匀分布(或接近于这样)平衡曲线。 我们提供了一个有效的确定性算法,用于通过V的(任意)查询点构造一个短的曲线列表,使得从列表中均匀随机选择的曲线上的随机点的分布在Fm上是ε-接近(在l1-范数下)均匀的。对于近似参数ε > 0,假设有N个查询点元组,该算法产生的列表的大小最多为O(N+1)。|Fm|)的。这使得随机有效验证和几乎线性的证明大小。该算法迭代地遍历查询点的所有元组对于每个元组,它以贪婪的方式选择通过该元组的曲线为此,它保持,对于每一点,→xFm,则在t → x处构造了时间S的n个berd(→x). 算法如下:1. F或every→x∈Fm,设d(→x)=02. 对于每一个querypi nts→x1的元组,. . . ,→xq,d,O(η/ε2)次,其中η表示|Fm|/N:通过和通过另一个点m(Fm)的曲线cur ves)。选择一条使总和最小的曲线→xCd(→x),其中C是c上所有点s→x的乘积,但设为→x1,. . . ,→xq.• 对于c上t→x的每一个点,d(→x)都在c中以→x的倍数递增. 注意,该算法在N中的时间多项式中运行,|Fm|和1.1.5组织第一部分提供了减少答案大小的方法,并作为对低程度测试和阅读的介绍[在我们的术语中,低程度阅读是在任意点s→x1上获得与低程度多项式一致的评价的过程。 . . ,→xq]。[12]的低度测试器及其对我们设置的适应在第3节中描述。低度阅读器(即,用于低度数读取的算法)使用标准(非随机性有效的)通过曲线的聚集作为过程是需要的,并且在第4节中描述。在第5节中介绍了使用[9]中的思想对其进行的改编。该机器允许我们构建一个次常数误差低次测试仪的几乎线性的大小与小的答案大小在第6节。聚合步骤由第7节中介绍的低度读取器启用。 这种低度阅读器是按照上述描述的方式以随机有效的方式实现的,并且使用在前面部分中开发的技术来减小答案大小。第7节还包含构造平衡曲线的算法及其分析。6j=1F|δ我.[|≥。|≥. .1L1MP roof. 设δ≥2。d,并假设存在l=[2π+1diffi=1i=1放大步骤和最后的PCP验证承诺在我们的主要定理是在第8节。2预赛2.1多项式域F上的m元多项式是函数Q:Fm→F,其形式为Q(x1,. . . ,xm)=ai,.,我xi1···ximi1,.,Im其中所有系数ai,.,我在F。表达式ai,.,ixi1· · ·xim被称为1m多项式的单项式1米1米Q的degre为:sdegQd=efmax,mIj|ai1,.,Im0,,其中,零多项式被定义为0。提案2.1. 固定一个域F和一个维数m。设Q1,Q2:Fm→F是两个多项式.则Q1+ Q2和Q1·Q2是F上的m元多项式,使得1. deg(Q1+ Q2)≤ max {deg Q1,deg Q2}。2. deg(Q1·Q2)≤ deg Q1+ deg Q2。[因此,对于多项式Q1,. . . ,Qk:Fm → F,则有deg(dkQi)≤ max {deg Q1,. . . ,deg Qk}i=1且deg(Qk Qi)≤kdegQi]对于维数为m,次数为d的域F,设Pm,d,F表示F上至多为d次的m元多项式族.Schwartz-Zippel引理表明,不同的低次多项式在大多数点上不同提案2.2(Schwartz-Zippel)。固定一个有限域F,维数m,度d。对于次数至多为d的两个不同多项式Q1,Q2:Fm→F,Pr[Q(→x)=Q(→x)]≤d21→x∈Fm|F|Schwartz-Zippel引理直接暗示了列表解码属性,建议2.3(列表解码)。一个有限域F和一个维数。M. Letf:Fm→F是某个函数,并考虑某个次数d≤|F|. 对于任何δ≥ 2,|d, if Q1,. . . ,Ql:Fm→F是次数至多为d的不同多项式,并且对于每个1≤i≤l,多项式在点的至少δr作用下,Q与f相等,即,Pr→x∈Fm[Qi(→x)=f(→x)]≥δ,则l≤2.|δ |δ多项式Q1,. . . ,Ql:如所述的Fm → F。defF或每一个1≤i≤l,令tAi={→x∈Fm|Q(→x)=f(→x)}。通过纳入-排除,LMi=1Ai.≥i=1|−|−i/=j|Ai∩ Aj|M7F|δ−IT,t0(t1)=0.Q∈−{}Σδd由Schwartz-Zippel,对于每个1 ≤ i/= j ≤ l,|AiAj|≤ |d·|Fm|. 因此,在前提下|≥ lδ| F m|−。|−.勒乌德|Fm|2|F|一方面,由于l >2,我们得到lδ >2。另一方面,由于2≤。|F|d≤|F|,我们获取. l≤ |F|. 这就产生了矛盾。插值固定一个有限域F。对于F上的一元多项式,对于k点的值的每一个固定,存在一个次数至多为k1的多项式,它与这个固定一致(并且这个多项式是唯一的Schwartz-Zippel)。让我们发展一些机制来论证这一点。提议2.4. 对于有限子集T<$F和t0∈T,设IT,t0 :F→F如下:对于每个x∈F,()=Qt∈T−{t0}(x−t)IT,t0 xQt∈T−{t0}(t0— t)的范围内则IT,t0是至多一次的一元多项式|不|− 1 over F,使得(i)IT,t0(t0)= 1;(ii) 对于每个t1∈T −{t0},它保持IT,t0(t1)= 0;(iii)对于每个x ∈F −T,它保持IT,t0(x)/= 0.证据 首先要注意,IT,t0至多是度|不|-1,因为t0∈ T,由命题2.1。1. 我 (t)=Qt∈T−{t0}(t0−t)= 1。T,t00Qt∈T−{t0}(t0−t)2. 设t1∈T−{t0}。 则Qt∈T−{t0}(t1−t)=(t1−t1)·Qt∈T−{t0,t1}(t1−t)=0。那么,3. 如果IT,t0(x)= 0,则t Tt0(x-t)= 0。因此,对于某个t∈T−{t0},(x−t)=0成立。 这不等于difx∈/T。命题2.5(单变量插值)。对于不同的标量t1,. . .,tk∈ F,以及x1,. . .,xk∈F,设Pt1,...,tk,x1,.,xk:F→F如下:对于每一个t∈ F,KPt1,...,t k,x1,.,x k(t)= I{t1,...,t k},t i(t)·xii=1那么,Pt1,...,tk,x1,.,xk是F上至多k − 1次的一元多项式,使得对于每1 ≤i≤k,它保持Pt1,.,tk,x1,.,xk(ti)= xi.证据 设1≤i0≤k. 然后,根据命题2.4,(i)+(ii),KPt1,...,t k,x1,.,x k(ti0)={t1,.,t k},t i(ti0)·xi = I{t1,.,t k},t i0(ti0)·xi0+xI{t1,...,tk},t i(ti0)·xi= xi02Di=1i ∈{1,.,k}−{i0}8ΣΣ我Kl=1l=1i1,.,Im11证明了对任意t ∈ F,c(t)=(c1(t),. . . ,cm(t))。对于每个t∈F,M11K1K引理2.6(多元插值)。设m为维数。考虑一个有限子集H<$F。然后,任何函数f:Hm→F都可以扩展为在most t m处具有degre e的多项式Qf:Fm→F(|H|−1)对于每个→x∈Hm,it成立Qf(→x)=f(→x).证据 我们使用命题2.4中用于单变量插值的符号。 对于每个(x1,. . . ,xm)∈Fm,令Qf(x1,. . . ,xm)=h1,...,h m ∈ HIH,h1(x1)··IH,hm(xm)f(h1,. . . (hm)Q:Fm → F是次数至多为m的多项式(|H|− 1),因为根据命题2.4,对于每一个1 ≤i≤m,多项式IH,hi(xi)的次数至多为|H|-1。此外,对于每个(hJ1,. . . ,hJm)∈ Hm,则Qf(hJ1,. . . ,hJm)=h1,...,h m ∈ HIH,h1(hJ1)··IH,hm(hJm)f(h1,. . . ,hm)= f(hJ1,. . . 、h、J、m)因为对于每一个H1,. . . ,hm∈Hsuc h that(h1,. . . ,hm)/=(h1J,. . . ,hJm),则存在1≤i≤m使得hii=hJi,因此,通过命题2.4,IH,hi(hJi)= 0,而IH,hJ1(hJ1)···IH,hJm(hJm)= 1。2.2曲线固定一个有限域F和一个维数m。定义3(曲线)。 Fm中的曲线是函数c:F → Fm,使得存在一元多项式c1,. . . ,cm:F →F,其中对任意t ∈ F,c(t)=(c1(t),. . . ,cm(t))。 程度是多项式的最大值:degcd=efmax{degc|1≤i≤m}。设Cm,F表示Fm中次数至多为k的曲线族.多项式Q:Fm→F对曲线c:F→Fm的限制是Q|c:F→F,对于每个t∈F,定义为Q|c(t)= Q(c(t))。命题2.7(多项式限制于曲线)。固定一个域F和一个维数m。对任意多项式Q:Fm→F和任意曲线c:F→Fm,|c是次数至多为deg c·deg Q的一元多项式。证据 表示Q(x1,. . . ,xm)=ai,.,我xi1···xim. 令c1,. . . ,cm:F → F是多项式我们有Q|c(t)= Q(c(t))= Q(c1(t),. . . ,cm(t))=ai,.,我(c1(t))i1·· ·(cm(t))im.通过命题2.1,对于每个1≤l≤m,(cl(t))il的次数至多为degcl·il≤ degc·il,并且(c1(t))i1 ···(cm(t))im的次数至多为<$mdegc·il≤ degc·<$mil≤ degc· degQ。因此,根据命题2.1,Q的次数|c至多为deg c·deg Q。我是被感染的。 对于不同的标量t1,. . . ,tk∈F,且(t未必不同)p∈ ns→x1,. . . ,→xk∈FM,我们将定义一个曲线,...,t,→x,. ,→x:F→Fm,满足对于任意1≤i≤k,e在t i处评估to→xi,即,ct1,.,tk,→x1,. ,→xk(ti)=→xi.F或每一个1≤i≤k,表示e →xi=(xi,1,. . . ,x1,m)。Mi1,.,ImM9→∈∈·| |·||||·| |Pt1,...,t k,x1,1,...,xk,1(t),. . . ,Pt1,.,t k,x1,m,...,x k,m(t)建议2.8(曲线拟合)。 Letct,.,t,→x,. ,→x:F→Fm是这样的,对于每个t∈F,1k1k.Σ[回想一下,Pt1的定义,...,tk,x1,l,...,xk,l出现在命题2.5中]然后,1. ct1,.,tk,→x1,. ,→xk是d eg re在mostk−1处的曲线。2. F或每个1 ≤i≤k,ct1,.,tk,→x1,. ,→xk(ti)=→xi.证据项1如下,因为对于每1 ≤l≤m,Pt1,.,tk,x1,l,...,xk,l的次数至多为k− 1,由命题2.5可知。第2项如下,因为对于每1 ≤ i ≤ k,对于每1 ≤ l ≤ m,我们再次由命题2.5得到Pt1,.,tk,x1,l,...,xk,l(ti)= xi,l.3大答案容量的随机有效低度测试器在本节中,我们描述了一个基于[12]中几乎线性尺寸的次常数误差低度检验的低度检验器测试器基本上与[12]中相同,只是我们以更方便的方式制定它,并证明了稍微不同的可靠性保证。测试器的目的是验证函数f:FmF的计算结果是(少数几个)低次多项式之一,方法是仅对f和的附加pro进行恒定数量的查询。测试结果为输入点t→xFm,在对F和附加证明提出质疑时作一些概率检验,并决定是否接受或拒绝。如果f确实是一个低次多项式,测试人员在提供了充分的证明后,应该以概率1接受任何输入。 而且,无论提供哪种函数f和证明,对于几乎所有的点,→x它对测试者的随机性具有很高的可预测性,当测试合格时,证明了f(→x)是与f相关联的几个低阶多项式之一在→x上的赋值.测试是如何进行的?若f是低次的,则它对Fm中任一仿射子空间的限制是低次多项式因此,作为一个证明,低次测试通常要求低次多项式,这些多项式被认为是f对某些低维仿射子空间族的限制。然后,以某种随机方式从该族中抽取出一个包含s → x的子空间,并将f(→x)与赋给s→x的多项式的值进行比较.[12]中使用的仿射子空间族是Fm中所有三维线性子空间的族,这些子空间由F上的一个向量和F的子域K上的两个向量所张成。 它表明,它是足够采取的子字段是小尺寸:K = poly(m),导致在家庭(和证明)的大小低于FmK2m=FmmO(m)。对于我们使用的域F和维数m,这确实是一个小族。证明的答案大小是描述F上的3变量低次多项式所需的位数。对于我们使用的度参数,这个答案的大小将太大。接下来的部分将允许我们减少它。注3.1. 我们[在这里和整篇论文中]更方便的是解决算法的随机性复杂性,而不是它的证明大小。注意,对于使用r个随机比特来查询其证明的q个位置的算法,有效地需要的证明的大小至多是q2 r。因此,对于对它们的证明进行恒定数量的查询的算法(像这里给出的所有算法一样),大小由2 r限制(直到常数因子)。ct1,.,tk,→x1,. ,→xk(t)=10M⊆SS∈→|M×典型代表。我们希望对三维线性子空间使用正则表示,因此函数f:Fm→F到子空间s的限制将被唯一地定义为函数fs:F3F。为了这个目的,让我们回顾一下线性代数中的一些事实对于域F上的矩阵M,M的行空间是其行所张成的线性子空间M的秩是它的行空间的维数域F上的两个相同维数的矩阵称为行等价,如果它们具有相同的行空间。定义4(行规范形式)。我们说一个域上的矩阵是行标准形的,如果它满足以下条件:• 所有非零行都在所有零行非零行的前导系数总是在它上面的行的前导系数的右边(如果存在这样的行• 前导系数是其列中唯一的非零项。• 所有前导系数均为1。事实3.2. 行标准型中矩阵的秩就是其中非零行的个数。事实3.3. 域上的每个矩阵都有唯一的行标准形的行等价矩阵。此外,高斯消除算法使用多项式(在矩阵的维度上)数量的字段操作来找到它。对于维数k,m和域F,设k,m,F是F上所有k m矩阵的行标准型族.由于每个维数至多为3的线性子空间s∈Fm是F上某个3×m矩阵的行空间,通过上述讨论,对每个维数至多为3的线性子空间s ∈ Fm,在3,m,F中存在唯一的矩阵,其行空间为s.我们用Ms表示这个矩阵,并用它来表示s。这允许我们定义函数f:Fm → F对s的限制唯一地为f|s:F3→F,其中f∈F3,|s(→t)=f(M T →t).如果给定向量→v1,→v2,→v3∈F m,且Fm的跨度为s,则可以通过对一个方向为→v1,→v2,→v3的矩阵进行高斯n消去来得到矩阵M s. 此外,对于每一个→x∈s,我们可以找到一个线性组合n→t对于其中M T →t=→x的F3(这将是恰好为3维的唯一f),使用poly(m)场运算,再次使用高斯消去。算法如下。算法随机有效低度测试器与大答案大小m,d,F,K。要求. m≥ 3是量纲参数。d是度参数。F是一个有限域,K<$F是它的一个子域,这样所有的域和子域操作(加法,乘法,域元素的采样等)都可以在F中进行。可以在时间多日志|F|.·11M → P.| ||F|| |K| ||F|F神谕该算法具有以下oracle访问权限:1. 函数f:Fm→F。2. 辅助证明神谕π:3,m,F3,d,F,假定分配给每个矩阵的多项式的次数最多为d,这是限制f的行空间的矩阵。输入.当t→x∈Fm时,我们希望t∈f.输出.要么接受,要么拒绝。保证(下面要证明)。完备性:对于每一个函数f,它是一个次数至多为d的多项式,存在一个预言机π的辅助proo,使得对于每一个输入t→x,测试r以概率1接受• 合理性:设εm,d,F,K=27m。.81 +4个| |md. F或f上的一个函数,当δ≥2时。d,存在l≤ 2/δ多项式Q1,. . .,Q1:Fm→F,次数至多为d,使得对于预言机π的每一个辅助概率,当→x在Fm中均匀分布时,概率y-≥→x且≥检验r所接受的检验r的随机数s,尽管f(→x)∈/{Q1(→x),. . . ,Ql(→x)}至多为δ+3εm,d,F,K+d+1.过程1. Pi ck到→ x的三维子空间。 在随机m→y1,→y2∈Km处,Pi c k是一致的. 得到矩阵M∈M3,m,F的行标准型,其行空间是F上由y→x,→y1,→y2 所张成的线性子空间. 如果→x,→y1,→y2线性地依赖于p∈ t,则c∈ t.2. 去子空间。通过计算求M上的yπ,并得到它在t→x点上的估计→t∈F3满足M T →t=→x,且y=π(M)(→t).3. 与点比较。查询yfon→x并比较两个值,如果y=f(→x),则接受;否则,拒绝。运行时间。步骤1:Pic king→y1,→y2可以在时间pl y(m,logg)中进行|F|)的。利用Gauss消去法,在时间poly(m,logF)中得到与y→x,→y1,→y2所生成的线性子空间相关联的矩阵M的新正则矩阵. 检查在M中的最后一次迭代是否为零时,在→x,→y1,→y2之间的线性相关性,这可以在时间多项式(m,log)中进行检查|F|).步骤2:计算→t∈F3,使得M T →t=→x可以在时间规划(m,logg)中使用高斯n消去法|F|)的。在t→ t上估计多项式π(M)可以在时间多项式(d,logg)中进行|F|).第3步:比较字段元素可以在时间多边形日志中完成|F|.因此,该算法的总运行时间为poly(m,d,log |F|).随机性。在步骤1中,测试r需要s2mlogKrandom比特stopick→y1,→y2。请注意,我们不知道可能需要d来选择t→x的p的随机数,t→x作为输入。·12∈M∈/ΣK.FF.联系我们≥≤→∈→Σ Σ≤1lm,d,F,KQueryComplexity.该测试对t → x上的函数f进行一次查询,对辅助证明预言机π进行一次查询,共两次查询.答案大小。 答案大小为poly(d,log |F|).正确性。引理3.4(完备性)。对于任意一个次数至多为d的多项式f,存在一个阶数为π的辅助pro,使得对于任意输入t →x,检验器以概率1接受.证据固定一个函数f,它是一个至多d次的多项式。对任意矩阵M∈ M3,m,F,定义π(M)为f对M上至多为3维的子空间的限制,即对于任意→t∈F3,π(M)(→t)=f(M T →t). 注意π(M)∈P3,d,F. 对于每一个输入t→x,在只有被检验r拒绝的每一个输入中,存在矩阵M3,m,F和标量→tF3,使得M T →t=→x和π(M)(→t)=f(→x),但这是不可能的,因为π(M)(→t)=f(M T →t).Lemma3.5(稳健性)。 Letεm,d,F,K=27m。.8|+。|+.4马里兰州对于任何函数f,对于任何|F|δ≥ 2|D|,存在l ≤ 2/δ多项式Q1,. . . ,Ql:Fm → F,次数至多为d,使得对于当→x在Fm中均匀分布时,检验器a在→x上和检验器随机性上的概率,尽管f(→x)/Q1(→x),. . . ,Q1(→x)至多为δ+ 3 εm,d,F,K + d+1.|F|证据固定一个函数f:Fm→F且δ≥ 2 |D|.设Q1,. . .,Ql是至多d次的所有不同多项式Qi,它们在至少δ个点的分数上与f一致,Pr→x∈Fm[Qi(→x)=f(→x)]δ。 根据第二项提议。3,有几个这样的多项式:l2/δ。假设矛盾的方式,有一个辅助证明甲骨文π,这样,当→x在Fm中是均匀分布的,在→ x和检验r的随机数上尽管f(→x)∈f{Q(→x),. . . ,Q(→x)}大于nδJd=efδ+3ε+d+1。|F|设t→x∈Fm,则f(→x)∈{Q1(→x),. . . ,Ql(→x)}。We将构造一个新的函数fJ:FmF,它在所有点上都与f相同,除了它分配解释的点不对应于至多d次多项式的值。 我们可以通过选择一个任意多项式QJ:Fm → F的次数精确到d+1,并让FJ分配解释p的值QJ(→x)。根据传统的假设,对于均匀分布的d→xFm→x和超过它所接受的测试r的随机数,在输入→ X时,给ORACLE访问J和TO Π,大于Δ J。根据[[12],定理2,译码],存在次数至多为d的多项式Q:FmF,使得PR→x∈Fm ≥δJ−3εm,d,F,K多项式Q和QJ必然不同,因为它们具有不同的阶数。此外,它们的度数都至多为d + 1。根据Schwartz-Zippel引理,+1个PR→x∈Fm Q(→x)=QJ(→x)d|F|13|F|≤ ≤∈ ∈{}∈∈≤≤∈| |因此,当Q(→x)=FJ(→x)且Q(→x)/=QJ(→x)时,p的分数ts → x ∈ Fm至少为δJ−3εm,d,F,K−d+1=δ。 当Q(→x)=FJ(→x)和Q(→x)/=QJ(→x)时,也有FJ(x)/=QJ(→x),并且也有FJ(→x)=f(→x). 因此,有至少tδ的分数ts→x∈Fm,(i)Q(→x)=f(→x);(ii)f(→x)∈/{Q1(→x),. . . ,Ql(→x)}。但这是不可能发生的:事实是(i)对于至少δ个点的一部分发生,意味着存在1i l,使得Q与Qi相同。另一方面,(i)和(ii)对于pis的正分数出现的事实暗示pit→x的存在Fm在其中Qi(→x)/Q1(→x),. . . ,Ql(→x),这是一个矛盾.注释3.6(与[12]的列表解码版本的比较)。注意,可靠性声明并不直接来自[[12],Theorem 2,List decoding]中出现的列表解码版本,因为(在某种意义上)那里的断言更弱:它只意味着对于每个函数f和辅助证明oracle π,存在列表解码。 这里我们断言,对于每个函数f,都存在一个列表解码[对所有π都一样]。另一方面,出现在[[12],定理2,列表解码]中的列表解码的概念比这里所要求的更强:这里示出了接受的概率,尽管分配给测试子空间的多项式不是Q1,. . .,Ql到子空间的距离是小的。我们只想论证这个经过检验的论点。4低度数阅读器与大答案大小在本节中,我们提出了一种称为低度阅读器的算法。该算法具有对π的oracle访问,假定编码低次多项式Q:Fm→F。该算法的目的是求p(s→x1,.) . . ,→xkFmit作为输入,只需要对π进行常量查询。如果算法检测到π不是低次多项式的有效编码,则允许拒绝。编码和读取器应具有以下两个属性:• 每个多项式都是可实现的:对于每个多项式Q:Fm→F,存在π来表示它。 在输入→x1时,允许对读取器进行访问。 . . ,→xkFm,输出Q(→x1),. . . ,Q(→xk)(概率为y1).• 低次多项式以高概率进行评估:对于每个π,一些低次多项式Q1,. . . ,Ql:Fm-F相关联(列表解码)。 对于每个元组e→x1,. . . ,→xk当读到的数据不被拒绝且输出为1时, . . ,ak,forsome1我我们知道,有一个vea1=Qi(→x1),. . . ,ak=Qi(→xk)[整个元组的i相同!]。该算法使用了第3节中的低次测试器,并应用了通过曲线聚集的技术。它不是我们构建的最终阅读器,因为它有两个缺陷:1. π的答案太大了:它多项式地依赖于次数,这对于我们使用的次数参数来说2. 它的随机性复杂度太高:每个输入元组需要超过mlogF个随机比特。 . . ,→xk.14Σi=1⊆4.1随机曲线该算法在s→x1,. . . ,→xkit作为输入,并在Fm中增加一个均匀分布的点.下面的命题表明,曲线上的每个点,但力d必须→x1,. . . ,→xk,是在Fm中均匀分布的。我们使用命题2.8的符号。命题4.1(随机曲线)。 Lett1,. . . ,tk∈F是不同的代数,且使得t→x1,. . . ,→xk∈F m. 设tk+1∈ F是不同于t1,. . .,tk. 设Xk+1均匀分布于Fm. 然后,对于每个t∈F−{t1,. . . ,tk},ct,.,t,t,→x,. ,→x,X(D)均匀单位为Fm。1Kk+1 1Kk+1P roof. Fixt∈F−{t1,. . . ,tk}。 记eXk+1=(Xk+1,1,. . . ,Xk+1,m),其中Xk+1,1,. . . ,Xk+1,m在F中均匀独立分布。记得ct1,.,tk,tk+1,→x1,. ,→xk,Xk+1(t)=.Pt1,...,t k,tk+1,x1,1,...,xk,1,Xk+1,1(t),. . . ,Pt1,.,tk,tk+1,x1,m,...,xk,m,Xk+1,m(t)设1 ≤l≤m。设a∈F. 我们将证明对于xk+1,l,x ∈ F存在一个值,使得Pt1,...,t k,tk+1,x1,l,...,xk,l,x(t)=a,并且thusPt1,...,tk,tk+1,x1,l,...,xk,l,Xk+1,l(t)在F中均匀分布. 建议如下。如命题2.5所示,KPt1,...,t k,tk+1,x1,l,...,xk,l,x(t)=I{t1,...,t k,tk+1},ti(t)·xi,l+1{ti,.,t k,tk+1},tk+1(t)·xi=1表示eAd=efkI{t1,.,tk,tk+1},ti(t)xi,l. 设Bd=efI{t1,...,tk,tk+1},tk+1(t)。 A和B都是标量在这个领域。请注意,由命题2。4,(i)+(iii),Bf=0,因为t∈f{t1,. . . ,tk}。那么,Pt1,...,tk,tk+1,x1,l,...,xk,l,x(t)= A + Bx. 方程A + Bx = a在变量x ∈ F中只有一个解x=(a−A)/B∈ F。4.2低度阅读器算法Low-Degree-Reader-With-Large-Answer-Size m,d,F,K,k.要求. m≥3是量纲参数。d≥1是度参数。 F是一个有限域,K F是它的一个子域,这样所有的域和子域运算(加法、乘法、域元素的采样、域中第i个元素的检索 可以在时间多日志|F|. k是要读取的点数 假设k ≤ |F|/2.神谕 该算法具有对π =(π1,π2,π3)的oracle访问,1. 一个函数π1:Fm→F,假定表示一个至多为d次的多项式。15M→ P
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功