---
_id: '3233'
abstract:
- lang: eng
text: 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.
alternative_title:
- LNCS
author:
- first_name: Johan
full_name: Håstad, Johan
last_name: Håstad
- first_name: Rafael
full_name: Pass, Rafael
last_name: Pass
- first_name: Douglas
full_name: Wikström, Douglas
last_name: Wikström
- first_name: Krzysztof Z
full_name: Krzysztof Pietrzak
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: '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'
apa: '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'
chicago: 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.
ieee: '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.'
ista: '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.'
mla: 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.
short: J. Håstad, R. Pass, D. Wikström, K.Z. Pietrzak, in:, Springer, 2010, pp.
1–18.
conference:
name: 'TCC: Theory of Cryptography Conference'
date_created: 2018-12-11T12:02:10Z
date_published: 2010-03-26T00:00:00Z
date_updated: 2021-01-12T07:41:59Z
day: '26'
doi: 10.1007/978-3-642-11799-2_1
extern: 1
intvolume: ' 5978'
month: '03'
page: 1 - 18
publication_status: published
publisher: Springer
publist_id: '3446'
quality_controlled: 0
status: public
title: An efficient parallel repetition theorem
type: conference
volume: 5978
year: '2010'
...