An efficient parallel repetition theorem

J. Håstad, R. Pass, D. Wikström, K.Z. Pietrzak, in:, Springer, 2010, pp. 1–18.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ; ;
Series Title
LNCS
Abstract
We present a general parallel-repetition theorem with an efficient reduction. As a corollary of this theorem we establish that parallel repetition reduces the soundness error at an exponential rate in any public-coin argument, and more generally, any argument where the verifier's messages, but not necessarily its decision to accept or reject, can be efficiently simulated with noticeable probability.
Publishing Year
Date Published
2010-03-26
Volume
5978
Page
1 - 18
Conference
TCC: Theory of Cryptography Conference
IST-REx-ID

Cite this

Håstad J, Pass R, Wikström D, Pietrzak KZ. An efficient parallel repetition theorem. In: Vol 5978. Springer; 2010:1-18. doi:10.1007/978-3-642-11799-2_1
Håstad, J., Pass, R., Wikström, D., & Pietrzak, K. Z. (2010). An efficient parallel repetition theorem (Vol. 5978, pp. 1–18). Presented at the TCC: Theory of Cryptography Conference, Springer. https://doi.org/10.1007/978-3-642-11799-2_1
Håstad, Johan, Rafael Pass, Douglas Wikström, and Krzysztof Z Pietrzak. “An Efficient Parallel Repetition Theorem,” 5978:1–18. Springer, 2010. https://doi.org/10.1007/978-3-642-11799-2_1.
J. Håstad, R. Pass, D. Wikström, and K. Z. Pietrzak, “An efficient parallel repetition theorem,” presented at the TCC: Theory of Cryptography Conference, 2010, vol. 5978, pp. 1–18.
Håstad J, Pass R, Wikström D, Pietrzak KZ. 2010. An efficient parallel repetition theorem. TCC: Theory of Cryptography Conference, LNCS, vol. 5978. 1–18.
Håstad, Johan, et al. An Efficient Parallel Repetition Theorem. Vol. 5978, Springer, 2010, pp. 1–18, doi:10.1007/978-3-642-11799-2_1.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar