(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,=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页未读,立即下载
- 粉丝: 5
- 资源: 2万+
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 深入浅出:自定义 Grunt 任务的实践指南
- 网络物理突变工具的多点路径规划实现与分析
- multifeed: 实现多作者间的超核心共享与同步技术
- C++商品交易系统实习项目详细要求
- macOS系统Python模块whl包安装教程
- 掌握fullstackJS:构建React框架与快速开发应用
- React-Purify: 实现React组件纯净方法的工具介绍
- deck.js:构建现代HTML演示的JavaScript库
- nunn:现代C++17实现的机器学习库开源项目
- Python安装包 Acquisition-4.12-cp35-cp35m-win_amd64.whl.zip 使用说明
- Amaranthus-tuberculatus基因组分析脚本集
- Ubuntu 12.04下Realtek RTL8821AE驱动的向后移植指南
- 掌握Jest环境下的最新jsdom功能
- CAGI Toolkit:开源Asterisk PBX的AGI应用开发
- MyDropDemo: 体验QGraphicsView的拖放功能
- 远程FPGA平台上的Quartus II17.1 LCD色块闪烁现象解析