We provide an overview of an analysis of the soundness error of parallel repetitions of general (i.e., two-sided error) interactive proof systems. The bottom-line is that the analysis of the general case, in which a majority decision is used, can be reduced to the analysis of the conjunction rule that is used in the one-sided error case. This reduction uses a general result of Panconesi and Srinivasan (SICOMP, 1997), which is worthy of wider familiarity. As a warm-up, we present a very simple reduction that can be used when the original interactive proof system has error probability that is smaller than 1/4.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Parallel Repetition of Interactive Proof Systems

  • Oded Goldreich

摘要

We provide an overview of an analysis of the soundness error of parallel repetitions of general (i.e., two-sided error) interactive proof systems. The bottom-line is that the analysis of the general case, in which a majority decision is used, can be reduced to the analysis of the conjunction rule that is used in the one-sided error case. This reduction uses a general result of Panconesi and Srinivasan (SICOMP, 1997), which is worthy of wider familiarity. As a warm-up, we present a very simple reduction that can be used when the original interactive proof system has error probability that is smaller than 1/4.