Ring-2

原文： Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

本文证明了对于 n 维立方体图的每一个拥有 ($2^{n-1}+1$) 个顶点的导出子图，其最大的度（degree）至少为 $\sqrt {n}$。这个结论优化了由 Chung, F¨uredi, Graham 以及 Seymour 在 1988 年证明的对数形式的下界（lower bound），并且可能是最优解。这个结论可以直接证明由 Nisan 和 Szegedy提出的理论计算机科学界著名猜想–布尔函数敏感度猜想（Sensitivity Conjecture），即布尔函数的敏感度和度是多项式相关的。

离散余弦变换(DCT)可以由离散傅里叶变换(DFT)推导得来。一维离散余弦变换根据输入序列的延拓方式不同有许多不同的定义式，常用的DCT-1定义为以下变换对: $$X^{c1}\left[ k\right] =2\sum_{n=0}^{N-1}\alpha \left[ n\right]x \left[n\right] \cos \left( \dfrac {\pi kn} {N-1}\right) ,0\leq k\leq N-1$$ $$x\left[ n\right] =\dfrac {1} {N-1}\sum _ {k=0}^{N-1}\alpha \left[ k\right] X^{c1}\left[ k\right] \cos \left( \dfrac {\pi kn} {N-1}\right) ,0\leq n\leq N-1$$