CLS hardness ⇒ PPAD hardness

Fully-black-box reduction · standard model · DP11 · security loss: none

Statement

$\mathbf{CLS}\subseteq \mathbf{PPAD}$: every problem in CLS reduces to End-of-Line by a polynomial-time map on instances together with a polynomial-time map taking solutions back — DP11. Hence if CLS is hard on average, PPAD is hard on average: pushing the hard distribution through the instance map gives an efficiently samplable distribution over End-of-Line instances on which every efficient algorithm finds a solution with negligible probability — standard.