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

文章基本信息

  • 标题:Competing-Provers Protocols for Circuit Evaluation
  • 本地全文:下载
  • 作者:Gillat Kol ; Ran Raz
  • 期刊名称:Theory of Computing
  • 印刷版ISSN:1557-2862
  • 电子版ISSN:1557-2862
  • 出版年度:2014
  • 卷号:10
  • 页码:107-131
  • 出版社:University of Chicago
  • 摘要:$ \newcommand\poly{\textrm{poly}} \newcommand\NC{\mathsf{NC}} $

    Let $C$ be a (fan-in $2$) Boolean circuit of size $s$ and depth $d$, and let $x$ be an input for $C$. Assume that a verifier, that knows $C$ but does not know $x$, can access the low degree extension of $x$ at one random point. Two competing provers try to convince the verifier that $C(x)=0$ and $C(x)=1$, respectively, and it is assumed that one of the provers is honest.

  • 关键词:communication complexity; competing provers; delegation; complexity theory
国家哲学社会科学文献中心版权所有