Concatenation Theorem

Concatenation Theorem in computational complexity theory extends hardness amplification to interactive settings. Where the Direct Product Theorem applies to non-interactive function computation, the concatenation theorem addresses protocols: if a prover has a small advantage in a single round of an interactive protocol, repeating the protocol independently makes the advantage vanish exponentially. The proof requires techniques from information theory and communication complexity, because the verifier can adaptively choose challenges based on prior responses. The theorem is essential for proving security of cryptographic protocols and for understanding the compositional behavior of computational complexity under repetition.

The concatenation theorem reveals that interaction does not escape the conservation laws of computational difficulty: even adaptive adversaries face exponentially amplified hardness when forced to win multiple independent games.