On the query complexity for Showing Dense Model
On the query complexity for Showing Dense Model
复制标题
关于显示密集模型的查询复杂度
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Jiapeng Zhang
中科院分区：
文献类型：
--
作者：
Jiapeng Zhang
绿色，陶和齐格勒的定理可以说如下：如果r是伪分布，而d是r的致密分布，则可以将d建模为均匀分布的分布m，以便d and d和d和M是不可分割的。关注查询复杂性以显示密集的模型，然后给出查询复杂性的最佳结合，我们还遵循Impagliazzo的硬核定理和Tao的规律性引理之间的联系，并通过规律性散至获得L2-Norm版本的硬质定理的证明。
A theorem of Green, Tao, and Ziegler can be stated as follows: if R is a pseudorandom distribution, and D is a dense distribution of R, then D can be modeled as a distribution M which is dense in uniform distribution such that D and M are indistinguishable. The reduction involved in the proof has exponential loss in the distinguishing probability. Reingold et al give a new proof of the theorem with polynomial loss in the distinguishing probability. In this paper, we are focus on query complexity for showing dense model, and then give a optimal bound of the query complexity. We also follow the connection between Impagliazzo’s Hardcore Theorem and Tao’s Regularity lemma, and obtain a proof of L2-norm version Hardcore Theorem via Regularity lemma.