德摩根公式与傅立叶浓度的关联：次二次大小与学习能力

本研究论文探讨了傅立叶浓度与布尔函数计算中的德摩根公式之间的紧密关系，特别是关注它们的大小和尖锐程度。德摩根公式在电路类设计，如AC0电路中，扮演着重要角色，其在理论计算机科学中的应用广泛，包括密码系统安全性、去随机化、电路复杂性分析以及算法设计。 论文首先明确了焦点，即次二次大小（或只读德摩根公式）与傅立叶质量的“小度”系数之间的联系。具体来说，对于一个由德摩根公式表示的布尔函数f，其大小s被证明有特定的傅立叶浓度界限。这种浓度与公式收缩指数r有关，例如德摩根公式中r=2，而对于某些特定类别的公式，如一次读取的德摩根公式，r=1/log2(51)3。这一发现对于理解电路类的设计效率以及相关算法设计具有实际意义。 作者进一步展示了与随机限制和小德摩根公式算法之间的关联，指出这些公式在AC0电路的浓度上达到了类似Linial、Mansour和Nisan论文中所述的性能，即A[n]中的傅立叶浓度满足|A|>s^(1/r) + e，当f属于A时，2^n ≤ exp(-sc/3)。这表明，对于小德摩根公式，其在计算上的收敛范围和复杂性分析方面有着显著的优势。 文章还探讨了这些公式与学习性、压缩性和平均灵敏度的关系。例如，次二次型大小的德摩根公式与宇称相关性不大，这意味着它们在均匀分布下的学习性良好，能在次指数时间内实现压缩。平均灵敏度方面，论文提供了关于只读德摩根公式严格界限的分析，表明其平均灵敏度大小为s的值为Θ(s^(1/Γ))，这与一般德摩根公式中已知的严格界限相呼应。 这项工作深化了我们对布尔函数计算中关键概念的理解，特别是德摩根公式与傅立叶分析之间的交互作用，对于优化电路设计和相关算法的复杂性分析具有重要的理论贡献。