# A Tight Parallel Repetition Theorem for Partially Simulatable Interactive Arguments via Smooth KL-Divergence

arXiv: https://arxiv.org/abs/2105.00801 · HTML: https://mlsanity.com/paper/2105.00801/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 May 2021.

## Built on by (most cited first, 1 of 1)

- [Smooth and Stepwise Self-Distillation for Object Detection](https://mlsanity.com/paper/2303.05015/) (2023)

## Abstract (arXiv)

Hardness amplification is a central problem in the study of interactive protocols. While ``natural'' parallel repetition transformation is known to reduce the soundness error of some special cases of interactive arguments: three-message protocols and public-coin protocols, it fails to do so in the general case. The only known round-preserving approach that applies to all interactive arguments is Haitner's random-terminating transformation [SICOMP '13], who showed that the parallel repetition of the transformed protocol reduces the soundness error at a weak exponential rate: if the original m-round protocol has soundness error 1-p, then the n-parallel repetition of its random-terminating variant has soundness error (1-p)p n / m4 (omitting constant factors). Hastad et al. [TCC '10] have generalized this result to partially simulatable interactive arguments, showing that the n-fold repetition of an m-round δ-simulatable argument of soundness error 1-p has soundness error (1-p)p δ2 n / m2. When applied to random-terminating arguments, the Hastad et al. bound matches that of Haitner. In this work we prove that parallel repetition of random-terminating arguments reduces the soundness error at a much stronger exponential rate: the soundness error of the n parallel repetition is (1-p)n / m, only an m factor from the optimal rate of (1-p)n achievable in public-coin and three-message arguments. The result generalizes to δ-simulatable arguments, for which we prove a bound of (1-p)δ n / m. This is achieved by presenting a tight bound on a relaxed variant of the KL-divergence between the distribution induced by our reduction and its ideal variant, a result whose scope extends beyond parallel repetition proofs. We prove the tightness of the above bound for random-terminating arguments, by presenting a matching protocol.