Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A Tight Parallel Repetition Theorem for Partially Simulatable
  Interactive Arguments via Smooth KL-Divergence   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 / m^4}$ (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 $\delta$-simulatable argument of soundness error
$1-p$ has soundness error $(1-p)^{p \delta^2 n / m^2}$. 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 $\delta$-simulatable
arguments, for which we prove a bound of $(1-p)^{\delta 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.

27
The categories of this paper are: comp-gas
35
The categories of this paper are: mtrl-th
36
The categories of this paper are: cmp-lg
26
The categories of this paper are: bayes-an
23
The categories of this paper are: solv-int
21
The categories of this paper are: adap-org
34
The categories of this paper are: chem-ph
11
The categories of this paper are: hep-lat
7
The categories of this paper are: hep-th
25
The categories of this paper are: patt-sol
12
The categories of this paper are: nucl-th
28
The categories of this paper are: alg-geom
16
The categories of this paper are: stat
31
The categories of this paper are: ao-sci
4
The categories of this paper are: cond-mat
5
The categories of this paper are: gr-qc