1DNF稀疏化与快速确定性计数算法微软硅谷研究院（Microsoft ResearchSilicon Valley）是一家总部位于美国硅谷的研究机构。ComRaghu Meka高级研究普林斯顿raghu@ias. 埃杜乌微软硅谷研究院OMER。我的朋友们，我的朋友们，我的朋友们。Com摘要给定n个变量的DNF公式f，两个自然的大小度量是项数或大小s（f）和项的最大宽度w（f）。 这是民间传说，短DNF公式可以缩小。 我们证明了一个相反的，表明狭窄的公式可以稀疏化。 更确切地说，任何宽度w DNF，无论其大小如何，都可以由w DNF wt tt（wlog（1/ε））O （w）terms来表示。我们将我们的稀疏化结果与Luby和Velikovic的工作结合起来[LV91，LV96]给出了一个快速的近似计算DNF满意解个数的确定性算法。给定一个含有poly（n）项的n元公式，我们的détérmin是O（loglog（n））的最小值，它表示一个détérminεp-逼近满足f（ε= 1/poly（logn））的赋值的分数. 的Luby和Velickovic在近20年前得到的最佳结果的运行时间为nexp（O（loglogn））[LV91，LV96]。·在硅谷微软研究院实习时完成的工作arXiv：1205.3534v1 [cs.CC] 2012年5月21介绍表示布尔函数f：{0，1}n→ { 0，1}的一种自然方法是将其写成CNF或DNF公式。允许这种形式的紧凑表示的函数类（又名多项式大小的CNF和DNF公式）是布尔函数分析的核心计算复杂性和机器学习。给定n个变量的DNF公式f，两个自然的大小度量是项数或大小s（f）和项的最大宽度w（f）。CNF的类似度量是子句数量和子句宽度。民间传说，每个具有m项的DNF公式f都可以被另一个DNFgε-近似，其中s（g）≤m且w（g）≤log（m/ε），而不管w（f）。公式g是通过简单地丢弃所有宽度大于log（m/ε）的项而获得的f的稀疏化。换句话说，短的DNF公式可以变得更窄。对于CNFs可以导出类似的陈述在本书中，我们展示了相反的联系：狭窄的公式可以变得简短。事实上，我们证明了存在一个强大的近似形式称为pseudorandomness是很重要的在这项工作中，我们只考虑逼近，也是布尔函数。定义1.1. 设f：{0，1}n→ {0，1}。 我们说函数f u，f n：{0，1}n→ {0，1}是f的ε-逼近器如果对任意x∈ {0， 1}n，f ∈（x）≤f（x）≤fu（x），且PRx∈{0，1}n[f（x）/=f（x）]=Prx∈{0，1}n[（f<$（x）= 0）<$（f（x）= 1）] ≤ε，PRx∈{0，1}n[fu（x）/=f（x）]=Prx∈{0，1}n[（f u（x）= 1）<$（f（x）= 0）] ≤ε。我们的主要结果是对任意宽度w，ε-逼近的存在性DNFs使用短宽度wDNFs，其中子句的数量仅取决于w和ε。定理1.1. 对任意宽w的DNF公式f和任意ε> 0，存在f的具有ε - s和具有p个x乘子的DNF公式f_n，f_h，f_h，f_h，f_h，m_s（wlog（1/ε））O（w）.我们的结果证明了DNF公式的稀疏化程序，其中使用的概念，由于罗斯曼[Ros10]的准向日葵沿着这些路线的最好的已知结果是由于Trevisan [Tre04]，他建立在Ajtai和Wigderson [AW85]之前的工作基础上。Trevisan证明了每个宽度为w的DNF都有ε-逼近器，它们是深度为d=O（w2w log（1/ε））的决策树。k-junta是一个只依赖于k个变量的函数。我们说f，g：{0， 1}n→{0， 1}，我们说g ε-逼近f，如果PRx∈{0，1}n[f（x）/= g（x）] ≤ε。我们的结果的一个推论是下面的DNF的junta定理。1 .我是一个很好的人。二、 对于任意的h-wDNF，ε-aprx由（wlog（1/ε））O（w）-junta表示。3一个类似的，但无与伦比的声明可以从Friedgut的军政府定理[ Fri98 ]。 很容易看出，宽度wDNF的平均灵敏度最大为2w1，因此根据Friedgut的计算，宽度wDNF的ε -闭合性为20 Ω（w / ε）-junt a。 Fri edgut的r e u lt give对w有更好的依赖性，而我们对ε有更好的依赖性。 Friedgut的近似器不是一个先验的小宽度DNF，并且人们不会得到精确的近似。Trevisan的结果意味着任何宽度w DNF都是ε -近似的k -junta，k = exp（O（w2 w log（1 /ε）[Tre 04]。定理1.1对其他参数设置有有趣的结果例如：推论1.3。对于n个变量，每个宽度为O（log n）的DNF公式都是n-O（1）接近于DNF时间复杂度为O（log n），空间复杂度为O（loglog（n））。在第6节中，我们猜想定理1.1中的一个更好的界是可能的，它在w中是单指数的。如果是真的，这个猜想将给出两个推论的更好的界1.2和1.3。1.1DNF计数和伪随机生成器CNF和DNF公式的满意解的数目估计问题与短种子长度公式的伪随机生成器的设计问题密切相关。这些问题已被广泛研究[KL 83，AW85，NW94，Nis91，LV91，LV96，LVW93，Tre04，Baz09，Raz09，DETT10]。对于公式f，令偏倚（f）=Prx∈{0，1}n[f（x）= 1]。给定函数类F中的公式f，函数类F的计数算法的目标是计算Bias（f）。我们将CNF和DNF的计数问题分别称为#CNF和#DNF精确计算Bias（f）的问题是#P-hard[Val 79]，因此我们看近似偏差（f）。如果算法的输出在[Bias（f）−ε，Bias（f）+ε]范围内，则算法给出Bias（f）的ε-加法近似很容易看出CNF和DNF的加法近似是等价的.有一个基于随机抽样的平凡的解决方案，但找到一个确定性的多项式时间算法已经证明是具有挑战性的。计算Bias（f）的乘法近似值更难，这里#CNF和#DNF的复杂性非常不同。如果一个算法的输出位于[Bias（f），cBias（f）]范围内，则称该算法为c-近似算法。很容易看出，获得一个多重近似的#CNF是NP-困难的. Karp和Luby给出了#DNF的第一个乘法近似，他们的算法是随机的[KL 83]。对于#DNF，加法近似和乘法近似之间存在一个简化：对于具有m项的DNF公式，计算（1+ε）-乘法近似的问题可以是1[Ama11]显示了w4.确定性地简化为计算#DNF的（ε/m）-加法近似的问题。这种减少在[LV 96]中明确说明，其中归因于[KL 83，KLM 89]对Karp-Luby算法进行去随机化是去随机化中的一个重要问题，从Ajtai和Wigderson的工作开始，该问题受到了很多关注[AW 85，LN90、LV91、LVW93、LV96、Tre04]。之前最好的结果是由于Luby和Velickovic[LV91，LV96]在近二十年前：他们给出了确定性的nexp（O（loglogn））时间算法可以计算任何固定常数ε的ε-加法近似。解决这个问题的一种自然方法是设计具有小种子的伪随机发生器（PRG），其可以欺骗深度为2的电路。这个问题及其推广到恒定深度电路是伪随机性的中心问题[AW85，NW94，Nis91，LV96，LVW93，Tre04，Baz09，Raz09，Bra10，DETT10]。定义1.4.一个生成元G：{0，1}r→ {0，1}nδ-愚弄一个函数类F，如果..PR..[f（G（y））] − Bias（f）. ≤ δ. y ∈{0，1} r.对所有f ∈ F. 如果G在r中按时间多项式可计算，则称生成子是显式的和n.一个种子长度为r的生成器，通过枚举所有的种子，在poly（m，n，2r）时间内对Bias（f）给出了一个ε这样的算法只需要黑盒访问f。约化形式[KL 83，KLM 89]暗示了种子长度为O（log（mn/ε））的DNFs的最优伪随机生成器将给出#DNF的确定性乘法近似算法。然而，由于De、Etesami、Trevisan和Tulsiani [DETT 10]，最知名的O（（log（mn/ε）2）. Luby-Velikovic算法是一种非黑盒算法，但用于小宽度DNF的PRG是一个重要组成部分。我们的结果我们利用稀疏化引理给出了n元宽为w的DNF公式类的一个更好的PRG，记为DNF（w，n）。2定理1.5. 对于所有δ，存在δ-fool的显式生成元G：{0，1}r→ {0，1}nDNF（w，n）且具有种子长度r=O..Σw2+w log1δΣ+log log（n）。相比之下，Luby和Velickovic [LV96]给出了一个种子长度为O（2w +log logn）的PRG，用于欺骗宽度wDNFs。注意，对于w=O（log logn）和δ常数，我们的算法的种子长度是O（loglogn）2，其中L是Luby，并且V是线性的，因此种子长度是O（logO（1）n）。对于w=loglogg（n）和dδ≥1/poly（n），则d-l长度h仍为On（loggn）.2 O（）tionti on用于确定gumets中的逻辑特性。5i=1利用我们的稀疏化结果，将任意项数的愚弄宽度wDNFs降为愚弄宽度wDNFs，得到了改进的小宽度DNF s生成器. 我们是被D.E.T.L. 在使用小偏差空间的情况下，事实上，我们的稀疏化给出了逼近器，这对这个结果至关重要。Luby-Velickovic计数算法可以被看作是一个（非黑盒）减少，从愚弄大小为poly（n）的DNF到愚弄更小宽度的DNF给出定理1.5，我们可以改进和简化他们的分析，得到一个更快的确定性计数算法。这是近20年来在这一问题上取得的首次进展此外，我们可以允许较小的ε值。定理1.6. 有一种确定性算法，当给定n上的DNF公式时，大小为m的变量作为输入，返回时间的Bias（f）的O（ε）-加法近似值. mn<$O<$（lo glog（n）+lo glog（m）+log（1/ε））ε当m≤p oly（n）且dε≥1/p oly（loggn）时，算法复杂度为O（nO（l o gl og（n）.H.S. S.它在计算学习[LMN 93，Man 95]和PRGconstructi o ns[AW85，GMR+12]中也有应用。当我们对所有的开关引理都有一个解时，我们给出了开关引理的一个部分去随机化我们获得的参数接近于Ajtai和Wigderson [AW85]的先前最佳结果，也许更重要的是，我们的论点在概念上更简单，涉及迭代应用我们的稀疏化结果和一个朴素的联合界。我们把细节推迟到第5。2DNF稀疏化我们将考虑指定为f=m的DNF公式其中表示为在以下意义上最小：• 每个Ti都是不恒定的。因此，每个项都是非空的（否则我们用1替换它），并且不包含变量及其否定（否则我们用0替换它这证明了Prx[Ti= 1] ≤1/ 2。• 每个Ti都不被另一个Tj所暗示;如果是这样，我们可以简单地从f的定义中删除Ti。这意味着，当被视为一组文字时，Tj/Ti。结果是TiTjTj。如果我们的稀疏化的某个阶段产生了一个不是最小的表示，我们可以将其转换为最小表示而不增加项数。如果一个DNF函数不包含一个变量和它的否定，我们称它为函数。6j=1i=12.1使用向日葵我们将首先证明定理1.1的以下较弱版本，其上界为（w2w ln（m/ε））w，并假设f是单态的。证明将说明我们的SPRIFICATION程序背后的关键思想定理2.1. 对任意宽度为w，大小为m且ε> 0的单元DNF公式f，存在多个f的DNF，f具有多个ε-逼近子，且f具有多个ε-逼近子.如果ICATionREUL是ERDA D OS-RADOSUNF L L emma[ER60]，则对我们的产品进行排序。定义2.1. 设k ≥ 3。 子集S1，. . . ，S k[n]是一种具有核心的向日葵对于所有i i，YifYi =Si i，并且对于所有i i = i i，dSii=Sii。 Si\Y的数据已重新计算了这些数据。我们考虑的集合系统将产生于单调DNF的某些最小表示中的项。这将确保花瓣总是非空的，尽管核心可能是空的。该celerbrdErdos-RadoSunflwerLemaguaranteveriet e定理2.2.（向日葵引理，[ER 60]）设F ={S1，. . . ，Sm}是[n]的子集的集合，每个子集的基数至多为w。 如果m> w！（k-1）w，则F有一个大小为k的向日葵。引理及其变体在复杂性理论中有几个应用，我们请读者参阅[Juk01，第7章]以了解更多细节。我们将用它来证明定理2.1。证据 （定理2.1的证明）固定一个unate，宽度wDNFf=T1<$T2<$··<$Tm，为简单起见，假设f是单调的。由于f是单调的，我们可以把每一项Ti看作是一组大小不超过w的变量。设k= 2w ln（m/ε）。提供.m≥w2w. 我的天lnε≥w！（k−1）w（2.1）向日葵引理保证了项T i1，. . . ，T ikwith a核心Y=10kTij 和不相交的花瓣Tij是的。因此，我们可以写Kj=1.Tij=YKj=1 （TijΣ\Y）=Yg，其中g=k（Tij\Y）。请注意，g是宽度为w且大小为k= 2w ln（m/ε）的只读DNF，因此它几乎肯定满足随机分配：Pr[g（x）=0]=XYki=1.Pr[Tij\Y=0]≤1−X1kε2w≤ m。第一个不等式成立，因为每个Tij\Y是一个宽度最多为w的项，第二个不等式成立是因为我们选择了k。∨∨7j=1因此，获得上界近似的一种自然方法是将g（x）替换为常数1，这相当于用Y代替了kTi。 设f′：{0， 1}n→ { 0，1}为J通过此替换获得的DNF公式显然f（x）≤f′（x）。此外，本发明还Pr[f（x）= 0 f′（x）= 1] ≤Pr [g（x）= 0] ≤ε。x xm最后，我们有s（f′）≤s（f）−（k−1）。我们现在可以迭代地应用上面的论点，只要项数是大于等式（2.1）中的边界。在每次迭代中，我们将s（f）减少k−1。因此，我们重复该过程至多m/（k-1）次，获得上近似公式fu，其中f（x）≤fu（x）<$x∈ {0， 1}n，Pr[f（x）/=fuXm ε（x）]≤·.k−1m。=ε，ΣΣs（fu）≤w2 wln mw.ε下面我们描述下近似公式f的构造。我们从向日葵Ti1，···，Tik开始，核心是Y。现在考虑从f中去掉一项得到的公式f′′，比方说Ti1。则f′′（x）≤f（x）。此外，它们两者仅在f ′′（x）= 0和f（x）= 1时不同，这发生在Ti1 = 1而Ti j = 0时，j ∈ {2，. . . ，k}。因此，我们可以将这个概率限制为：Pr[f′′（x）/=f（x）]=Pr[Ti= 1]·Pr[（kT i）= 0|我不是= 1]x xj1xj=2jJ1 .一、1k−1 ε=Pr[（kTi\Y）= 0]= 1− ≤2xj=2j2 2WM其中第二个不等式成立，因为根据向日葵的性质，条件Ti1= 1固定了核心Y= 1，但不影响其他花瓣。注意s（f′′）≤s（f）−1。我们现在将这一步重复不超过m次，以获得公式f，其中f<$（x）≤f（x）<$x∈ {0， 1}n，Pr[f]（x）εf（x）]≤m·=ε，X.M .ΣΣs（fu）≤w2 wln mw.ε定理2.1比定理1.1在不确定性、对m的依赖性和对w的依赖性方面弱。我们简单地描述一下如何处理前两个问题。1. 不和谐。 我们可以通过使用引理2.7来去除这个假设，它保证了任何DNF公式都包含一个大子公式。由此产生的语句对于推论1.3已经足够了，因为任何宽度为log（n）的DNF最多可以有n个O（log（n））的子句。8i=1j=1i=1i=12. 依赖M。逼近器的大小在数学上取决于m。 我们可以通过观察到当公式大小很大时，稀疏化的每一步产生的误差都很小来避免这一点我们可以使用这个参数来得到一个（2wln（1/ε））O（w）的大小bond，其中ich是m的整数倍。3. 依赖于W。最终的界限是关于w2的指数而不是w。这来自向日葵引理中的（k−1）w项，我们将其应用于k= 2w。问题是，W！向日葵引理中的项是必要的是组合数学中的一个但有一个下界（k-1）w[Juk 01]。因此，即使下限是正确的答案，它也不（直接）意味着更好的答案。定理2.1。2.2使用准向日葵进行稀疏化。我们在定理2.1中使用的向日葵系统的主要性质是花瓣上的公式g高度偏向1。如Rossman[Ros 10]所示，可以保证存在这样的“quasi-sunflower”系统满足这个较弱的性质，即使在项数比通常的向日葵引理小得多的情况下我们调整我们的论点，使用准向日葵而不是向日葵，以获得定理1.1。我们将使用Rossman [Ros10]提出的准向日葵的概念。定义2.2.（Quasi-Sunflowers，[Ros 10]）一个唯一的DNF公式h = k其中k≥2是一个γ-拟向日葵，其核心Y=kTi，花瓣{Ti\Y}k，如果Pr[k（T i\Y）= 1] ≥1 − e−γ。Xi=准向日葵在某种意义上扩展了向日葵的概念，即即使我们不允许k= 1，因为否则每一项都是平凡的拟向日葵。因为我们坚持一个DNF的任何项都不包含在另一个DNF中，所以花瓣是非空的。因此，每个花瓣满足的概率最多为1/ 2，因此每个γ-向日葵都有k=<$（γ）个花瓣。引理2.3.（Quasi-Sunflower引理，[Ros 10]）任意单端宽度为w的DNF公式项包含γ（m）-拟向日葵，其中1 .一、m/wγ（m）：=5w！.（二、二）罗斯曼用集合系统的语言陈述了这个结果，我们用DNFs的语言重新表述了我们在附录中证明了两者的等价性。下面的引理将用于分析我们稀疏化的一个步骤引理2.4. 设g=m我是一个不迟到的DNF。然后Pr[（T1= 1）<$（（kTi）= 0）]≤Pr[（kTi）= 0]。xi=2xi =19i=1i=1j=1证据 不失一般性地假设g是单调的。由于g中的每一项也是单调的，KleitmanPr[（T1=0）<$（（kTi）=0）]≥Pr[T1=0]·Pr[（kTi）= 0]xi=2x xi =2Pr[（T1= 1）]（（kTi）=0）]≤Pr[T1=1]·Pr[（kTi）= 0]X所以我们有I=2x xi=2Prx[（T1= 0）<$（（kTi）=0）]Prx[（T1= 1）<$（（kTi）= 0）]i=2≥Pr[（λkT i）= 0] ≥i=2。Prx[T1=0]但这意味着，xi=2Prx[T1=1]Pr[（T= 1）（（kT）=0）]≤Pr[（λkT）= 0]·Prx[T1= 1]≤Pr[（tkT）= 0]x1i=2ixi=1iPrf[T1 = 0]xi=1i其中最后一个不等式如下，因为对于任何（非空）项T，Pr[T = 1] ≤1≤Pr [T = 0]。（二、三）X2xT1的唯一正确性是Prx [T1=1]≤Prx[T1=0]。我们可以去掉满足Prx[Ti∈STi= 1]≤Prx[Ti ∈STi= 0]的任何项集{Ti}i∈S以下是我们的关键技术引理。它适用于一元公式，并允许我们将公式的大小减少（至少）1。引理2.5. 对于每个单端宽度-w DNF公式g，存在宽度-w DNF对于多个示例，gueachofsizeatm−1 tare−γ（m）s，并wichingaproximatorsforg。证据 设g = mT i.引理2.3保证了γ（m）-拟向日葵的存在ki=1 Tij 其中γ（m）由公式（2.2）给出。设p（x）=k（Tij（B）be the对于p（x）=0，Prx≤e−γ（m）.我们可以写h（x）=kTij.=YKj=1 （TijΣ\Y）=Yp（x）我们通过替换g（x）得到了一个上界DNF公式gu：{0，1}n→ { 0，1}p（x）乘以常数1，这相当于用核心Y代替h（x）。很明显g（x）≤ g u（x），s（g u）≤ s（g）−（k − 1）≤ s（g）− 1。此外，本发明还h=0∨10Pr[g（x）/=gu（x）] =Pr[（g（x）= 0）<$（gu（x）= 1）]X x≤Pr[p（x）= 0]X≤e − γ（m）。10j=2i=1我们现在构造下半近似。设g是从g中去掉项Ti1得到的公式。那么，很明显，g（x）≤g（x），s（g）≤s（g）− 1。此外，本发明还Pr[g（x）/=g（x）] =Pr[g（x）= 1g（x）= 0]X x≤Pr[（（Ti1X\Y）= 1）（k（Tij（\Y））= 0]≤Pr[p（x）= 0]（根据引理2.4）X≤e − γ（m）。通过反复应用这个引理，我们可以证明定理1.1为了处理一般情况，我们使用下面的简单引理来减少构造unate近似的问题引理2.6. 设f，g，h：{0，1}n→ {0，1}使得f = g <$h。设g∈ G，gu是g的ε-逼近算子 则g h和g uh是f的ε-逼近器。证据 很容易看出，对于每个x∈ {0， 1}n，g（x）h（x）≤ g（x）h（x）≤ g u（x）h（x）.我们给出了gh的逼近误差的界，guh的证明也是类似的。Pr[（g<$（x）<$h（x））/=（g（x）<$h（x））]=Pr[（g<$（x）<$h（x）= 0）<$（g（x）<$h（x）= 1）]X x=Pr[（g<$（x）= 0）<$（g（x）= 1）<$（h（x）= 0）]X≤Pr[（g<$（x）= 0）<$（g（x）= 1）]X≤ε。引理2.7. 对于每个宽度wDNFf=mTi的大小为m，存在S[m]，其中|≥ m/ 2 w使得公式g = j ∈ S T i|≥ m/2wsuch that the formula g = ∨j∈ST i是unate。证据随机选取一组文字S如下：对于每个变量xi，如果或仅为一个tr和dom，则将xi或x<$i中的一个加到oSun。LetgSbethet gS b ethe t g-fffrmedfrmscontain ing仅来自S的文字。那么，gS总是unate。每一项都至少有2−w的机会在gS中。根据预期的线性E[s（gSSJ10M）]≥ 2w.11i=1ℓuℓu我们将使用下面的渐近界，其证明是一个计算，并推迟到附录。事实2.8. 对于由等式2.2定义的γ：R+→R+，W=（2w）3w（50 log（1/ε））w，并且ε≤1/ 4，现在我们可以证明定理1.1：布勒姆j=W+1e−γ（j/2w）≤ ε。证据 设f = mT i. 通过应用引理2.7，我们可以写f=gh，其中g是单端的并且有m′≥m/2w项。由引理2.5可知，存在逼近算子g∈，gu每个宽度为w，大小至多为m′-1，其误差由下式限定：e−γ（m′）≤e−γ（m/2w）。根据引理2.6，f1=gf1=guh是一个re−γ（m′）s，并且对于f，wi chi n g是一个proxi mati o ns。进一步s（f1）=s（g）+s（h）≤s（g）−1+s（h）≤s（f）−1类似地，s（f1）≤s（f）−1。我们分别对上、下逼近器构造这个结构，直到其大小的公式下降到W以下。这给出了序列f（x）≤f1（x）···≤fku（x）：=fu（x）乌乌f（x）≥f1（x）···≥fk<$（x）：=f<$（x）ℓℓ其中s（f_u），s（f_u）≤W.我们可以通过以下方式限制这些近似器的误差：布勒姆j=W+1e−γ（j/2w）≤ε。（2.4）其中不等式来自事实2.8。这就完成了定理1.1的证明。3欺骗小宽度DNF接下来，我们使用我们的稀疏化结果来构造小宽度DNFs的伪随机生成器，在Luby和Velickovic [LV96]的生成器上获得宽度方面的指数改进。我们用r的精确渐近性重申定理1.5。定理3.1. 对所有δ，存在一个显式生成元G：{0，1}r→ {0，1}n，δ-fool所有宽度wDNFs，且种子长度为R=O..Σw2log2（w）+wlog（w）log1δ12Σ+ log log（n）13.x←D.我们证明定理如下：首先利用我们的稀疏化结果，将任意项数的宽度为wDNF s的情况简化为宽度为wDNF s的情况，其中h为2O（w ）ter m，并且由于Detal的存在，宽度为wDNF s的情况。[DETT10]显示具有小偏置空间的DNF具有很少的项。定义3.2（k-ε-偏置空间）. {0，1}n上的分布D称为（k，ε）-偏置空间，如果对于每个大小至多为k的非空子集I∈[n]... Pr[i∈Ixi= 1]−.1 .一、. ≤ε。2Naor和Naor [NN 93]构造了显式的（k，ε）-偏置空间，只需要O（k+ log（1/ε）+log logn）位来采样。接下来，我们需要De等人的以下结果。[DETT 10]表明（k，ε）-偏置空间欺骗DNF s以选择合适的k和ε。定理3.3. [DETT 10，定理4.1]对于每个δ> 0，每个宽度为w且大小为m被（k，ε）-有偏分布δ-愚弄，k=O. Σ1.w日志.. m、δ. m日志ε= O w log（w）log。δDe等人 仅对k = n的情形证明了上述陈述，并且他们使用了界w ≤log（m/δ）。他们的证明过程中，通过构造小的numer1-norm-numering逼近。上面的陈述是通过重复他们的证明得到的，保持w和m分开，并限制所得逼近器的次数和从他们的证明中很容易看出，逼近器的次数k≤O（wlog（m/δ））和范数b（m/δ）为O（wlog（w））.我们利用这样一个事实，即要欺骗一类函数，只要欺骗近似的函数就足够了mators [BGGP07，Baz09].事实3.4.设F，G是函数类，使得每个f ∈ F在G中有ε-逼近子. 设G：{0，1}r→ {0，1}n是ε-愚弄G的伪随机生成元. 则G（ε+δ）-foolsF.现在我们准备证明本节的主要结果定理3.1的证明 回想一下，DNF（w，n）表示n个变量上所有宽度为w的DNF s的类。设G ∈DNF（w，n）表示所有公式的子集，其大小至多为m=（wlog（1/δ））cw，且c足够大.由定理1.1可知，任意f∈DNF（w，n）在G中都有δ-逼近。接下来，我们应用定理3.3，其中m=（wlog（1/δ））cw。注意日志. mδ.=Owlog（w）+log. ΣΣ1.δ14j=1因此我们得出结论，（k，ε）-有偏分布δ-foolG，其中k=O. Σ.w2log（w）+wlog.. ΣΣ1δ。ΣΣ1日志ε=Ow2log2w + w log（w）log1 。δ请注意，我们可以使用长度种子从这样的分布中采样R=O..Σ1k+ log.εΣ+ log log（n）. Σ Σ=O w2 log2（w）+wlog（w）log1δ+ log log（n）最后，根据事实3.4，这样的分布2δ欺骗了类DNF（w，n）。4DNF的确定性计数我们现在在Luby-Velickovic计数算法[LV 96]中使用PRG来处理上一节中的小宽度DNF更好的种子长度意味着我们不需要仔细地平衡各种参数，并且可以用更简单和更好的参数设置来重做它们的参数。我们算法的输入是一个DNF公式f=mTj，n个变量的大小为m，宽度w，输出是Bias（f）的ε-加法近似。我们设置以下参数k：= log. wε，t：=w，w′kε= 6k，δ =不LetH={h：[n]→[t]}是k-维空间的一个族，它具有hfuns. Fixahash函数h ∈ H，设Bj={i：h（i）= j}. 我们称Tibad为h，如果M a x|BjTi|>w′j∈[t]这里我们把Ti看作一组变量。设fh是从f中去掉所有对h不利的项后得到的公式。设G：{0， 1}r→ { 0， 1}n是定理1.5中的生成元，它欺骗DNF（w′，n）的误差不超过δ.定义一个新的生成元Gh：（{0， 1}r）t→ {0， 1}n如下：Gh（z1，. . . ，zt）=x，其中对于j∈[t]，x|Bj=G（zj）。（4.1）因此，G h将G的独立副本应用于由散列函数h定义的每个桶。15我们现在陈述计数算法：16i=1K算法DNFCount对于eachh∈H，Dropallbadermsforhfrobtanfh. 通过numerationveralz∈{0，1}rt，computeph=Prz∈{0，1}rt[f h（G h（z））= 1].（4.2）ReturnpH=maxh∈Hph.我们需要以下关于k-独立散列函数的引理。引理4.1. 设H：[n] → [t]是一个k-独立的散列函数族。 每一个人，都有一个属于自己的故事。|S|[001 pdf 1st-31 files]每个人都有自己的故事。PRh∈uHΣΣ|≥6k|≥6k≤2 −k。证据 固定j ∈ [t]。 令S ={1，. . . ，kt}而不失一般性。 令{X i}kt成为指标随机变量，如果h（i）=j则为1，否则为0。然后好 吧ΣΣEh∈HYXi≤KT1k·tk ≤e k。应用马尔可夫我说，|我|=k i∈IPRh∈uHΣ|h−1Σ（j）国家统计局|≥ 6 k杨永≤。6k≤2 −。K我们的分析需要[LV96]中的两个引理由于他们的术语和符号与我们的不同，我们在附录B中提供了这两个引理的证明。第一个引理将fh的偏差与f的偏差联系起来。引理4.2. [LV96，引理11]我们有当f∈ H时，Bias（fh）≤Bias（f），E [Bias（f h）] ≥Bias（f h）−ε。h∈H下一个引理表明Gh欺骗公式fh本质上是[LV96，引理7]。回想一下，通过公式（4 - 2），ph是在由Gh生成的分布下fh的偏置。17引理4.3. [LV96，引理7]我们有|p h−Bias（f h）|≤ε。18twε有了这些引理，我们现在分析算法。定理4.4. 算法DNFCount当给定n个变量的DNF时，宽度为w，大小为m作为输入，在时间上返回Bias（f）的O（ε）-加法近似O（nO（l og（w/ε））（loggn）O（w）2O<$（wl og（1/ε））m）.证据算法的正确性很容易争论。对于每个h∈ H，ph≤Bias（fh）+ε（根据引理4.3）≤Bias（f）+ε（根据引理4.2）进一步根据引理4.2，存在h∈ H使得Bias（fh）≥Bias（f）−ε，因此根据引理4.3，p h≥ Bias（f h）− ε ≥ Bias（f）− 2 ε。因此，pH是2ε-加法近似偏差（f）。我们现在限制运行时间。对任意h∈ H计算fh，并在对于z∈ {0， 1}rt，Gh（z）可以在时间O（mn）内完成.因此，运行时间由|2室温。|2 rt. 通过标准的k-方向独立散列函数的构造|H|时间复杂度O（k）接下来，我们绑定种子长度r。记得k= log. wε kε，δ==. 1美元 。w因此logδ= logεk=k − log（k）。此外，w′= 6k。因此，定理3.1，.. Σ ΣR=Ow′2log2（w′）+w′log（w′）log1δ+ log log（n）时间复杂度：O（n）rt=O.（k2KΣlog2（k）+ log log（n））时间复杂度为O（wk log2k + w log log（n））。所以我们得到W
我的内容管理
展开
