---
res:
bibo_abstract:
- We prove a negative result concerning error reduction by parallel repetition for
computationally sound protocols, e.g., interactive arguments. Our main result
is a complete and computationally sound eight round interactive argument for which
k-fold parallel repetition does not reduce the error below a constant for any
polynomial k. The starting point for our construction is the work of Bellare,
Impagliazzo and Naor (FOCS'97). For any fixed k, they construct a four round protocol
for which k-fold parallel repetition does not lower the soundness error. The communication
complexity of this protocol is linear in k. By using universal arguments due to
Barak and Goldreich (CCC 2002), we turn this protocol into an eight-round protocol
whose complexity is basically independent of k. @eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Krzysztof Pietrzak
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9139-1654
- foaf_Person:
foaf_givenName: Douglas
foaf_name: Wikström, Douglas
foaf_surname: Wikström
bibo_doi: 10.1007/s00145-010-9090-x
bibo_issue: '1'
bibo_volume: 25
dct_date: 2012^xs_gYear
dct_publisher: Springer@
dct_title: Parallel repetition of computationally sound protocols revisited@
...