首页    期刊浏览 2024年12月01日 星期日
登录注册

文章基本信息

  • 标题:Direct Product Testing With Nearly Identical Sets
  • 本地全文:下载
  • 作者:Dana Moshkovitz
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In this work we analyze a direct product test in which each of two provers receives a subset of size n of a ground set U, and the two subsets intersect in about (1-\delta)n elements. We show that if each of the provers provides labels to the n elements it received, and the labels of the two provers agree in the intersection between the subsets with non-negligible probability, then the answers of the provers must correspond to a certain global assignment to the elements of U.

    While previous results only worked for intersection of size at most n/2, in our model the questions and expected answers of the two provers are nearly identical. This is related to a recent construction of a unique games instance (ECCC TR14-142) where this setup arises at the ``outer verifier'' level.

    Our main tool is a hypercontractive bound on the Bernoulli-Laplace model (aka a slice of the Boolean hypercube), from which we can deduce a ``small set expansion''-type lemma. We then use ideas from a recent work of the author about ``fortification'' to reduce the case of large intersection to the already studied case of smaller intersection.

  • 关键词:Bernoulli-Laplace model ; direct product testing ; hypercontractivity ; Parallel Repetition
国家哲学社会科学文献中心版权所有