首页    期刊浏览 2024年11月29日 星期五
登录注册

文章基本信息

  • 标题:Parallel Repetition: Simplification and the No-Signaling Case
  • 本地全文:下载
  • 作者:Thomas Holenstein
  • 期刊名称:Theory of Computing
  • 印刷版ISSN:1557-2862
  • 电子版ISSN:1557-2862
  • 出版年度:2009
  • 卷号:5
  • DOI:10.4086/toc.2009.v005a008
  • 出版社:University of Chicago
  • 摘要:

    Consider a game where a referee chooses (x,y) according to a publicly known
    distribution; sends x to Alice, and y to Bob. Without communicating
    with each other, Alice responds with a value a and Bob responds with a
    value b. Alice and Bob jointly win if a publicly known predicate
    Q(x,y,a,b) is satisfied.

    Assume that the maximum probability that Alice and Bob can win in
    such a game is v < 1. Raz (SIAM J. Comput. 27, 1998) shows that if
    the game is repeated n times in parallel, then the probability
    that Alice and Bob win all games simultaneously is at most
    (v')^{n/log(s)) where s is the maximal number of possible responses
    from Alice and Bob in the initial game, and v' is a constant depending
    only on v.

    In this work, we simplify Raz's proof in various ways and thus
    shorten it significantly. Further we study the case where Alice and
    Bob are not restricted to local computations and can use any
    strategy which does not imply communication between them.

  • 关键词:parallel repetition; probabilistically checkable proof
国家哲学社会科学文献中心版权所有