1998/06/01 by Ran Raz · 729 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Machine Learning and Algorithms #Repetition (rhetorical device) #Logarithm #Constant (computer programming) #Constructive #Discrete mathematics #Exponent #Mathematics #Exponential function #Computational complexity theory #Combinatorics #Calculus (dental) #Computer science #Algorithm #Mathematical analysis
paper · doi:10.1137/s0097539795280895
published in SIAM Journal on Computing 27(3), 763-803 (Society for Industrial and Applied Mathematics)
openalex publication_date 1998/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
We show that a parallel repetition of any two-prover one-round proof system (MIP(2,1)) decreases the probability of error at an exponential rate. No constructive bound was previously known. The constant in the exponent (in our analysis) depends only on the original probability of error and on the total number of possible answers of the two provers. The dependency on the total number of possible answers is logarithmic, which was recently proved to be almost the best possible [U. Feige and O. Verbitsky, Proc.11th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, Los Alamitos, CA, 1996, pp. 70--76].