首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:Advice Lower Bounds for the Dense Model Theorem
  • 本地全文:下载
  • 作者:Thomas Watson
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2011
  • 卷号:2011
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We prove a lower bound on the amount of nonuniform advice needed by black-box reductions for the Dense Model Theorem of Green, Tao, and Ziegler, and of Reingold, Trevisan, Tulsiani, and Vadhan. The latter theorem roughly says that for every distribution D that is -dense in a distribution that is -indistinguishable from uniform, there exists a ``dense model'' for D, that is, a distribution that is -dense in the uniform distribution and is -indistinguishable from D. This -indistinguishability is with respect to an arbitrary small class of functions F. For the natural case where () and O(1), our lower bound implies that (1)log(1)logF advice bits are necessary. There is only a polynomial gap between our lower bound and the best upper bound for this case (due to Zhang), which is O(12)log(1)logF . Our lower bound can be viewed as an analog of list size lower bounds for list-decoding of error-correcting codes, but for ``dense model decoding'' instead.

国家哲学社会科学文献中心版权所有