Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution
复制标题
规律性、增强和有效模拟每个高熵分布
DOI：
10.1109/ccc.2009.41
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
S. Vadhan
中科院分区：
文献类型：
--
作者：
L. Trevisan;Madhur Tulsiani;S. Vadhan
我们表明，每个有界函数g：{0,1}^n -≫ [0,1]接受一个有效计算的“模拟器”函数H：{0,1}^n -≫ [0,1]，使每个固定的每个固定多项式尺寸电路与G与H具有大致相同固定多项式的电路与D无法区分大小。 Frieze和Kannan的弱Szemeredi规律性引理（B）具有更好的定量参数（多项式而不是指数级）的绿色，道和Ziegler的密集模型定理的建设性版本在区分概率中），（c）脱落的硬核套件。理论。我们提出了我们的结果的两个证据，这是一个通过线性编程的双重性来证明了尼桑的证明，一种类似于Impagliazzo的“增强”证明通过迭代分区进行的第三个证明，这使采样器的复杂性在区别概率中是指数的，也隐含在密集模型定理的绿色-tao-Ziegler证明中。
We show that every bounded function g: {0,1}^n -≫ [0,1] admits an efficiently computable "simulator" function h: {0,1}^n-≫[0,1] such that every fixed polynomial size circuit has approximately the same correlation with g as with h. If g describes (up to scaling) a high min-entropy distribution D, then h can be used to efficiently sample a distribution D' of the same min-entropy that is indistinguishable from D by circuits of fixed polynomial size. We state and prove our result in a more abstract setting, in which we allow arbitrary finite domains instead of {0,1}^n, and arbitrary families of distinguishers, instead of fixed polynomial size circuits. Our result implies (a) the Weak Szemeredi Regularity Lemma of Frieze and Kannan (b) a constructive version of the Dense Model Theorem of Green, Tao and Ziegler with better quantitative parameters (polynomial rather than exponential in the distinguishing probability), and (c) the Impagliazzo Hardcore Set Lemma. It appears to be the general result underlying the known connections between "regularity" results in graph theory, "decomposition" results in additive combinatorics, and the Hardcore Lemma in complexity theory. We present two proofs of our result, one in the spirit of Nisan's proof of the Hardcore Lemma via duality of linear programming, and one similar to Impagliazzo's "boosting" proof. A third proof by iterative partitioning, which gives the complexity of the sampler to be exponential in the distinguishing probability, is also implicit in the Green-Tao-Ziegler proofs of the Dense Model Theorem.