The reduction conjecture from temporal cliques to Erdős–Rényi cliques

Let ${\cal G}_{n,\delta}$ denote the Erdős–Rényi random graph model with edge probability $\delta$, and let $(K_n,\lambda)$ be a random simple temporal graph. A $\delta$-clique is a vertex set whose edge labels lie within some interval of length $\delta$. Write $k_0=\frac{2\log n}{\log(1/\delta)}$, and let $\mathcal A_{SRT}(\delta)$ be an algorithm for random instances of $(K_n,\lambda)$. Reduction conjecture. Suppose that, for any $\delta\in[0,1]$, there is a polynomial-time algorithm $\mathcal A_{SRT}(\delta)$ that finds an $(1-o(1))$-approximation of a maximum $\delta$-clique in a random instance of $(K_n,\lambda)$ with high probability. Then $\mathcal A_{SRT}(\delta)$ can be used to design a polynomial-time algorithm that finds an $(1-o(1))$-approximation of a maximum clique in ${\cal G}_{n,\delta}$ with high probability. This conjecture formalizes a possible average-case reduction between finding large temporal cliques and finding large cliques in Erdős–Rényi random graphs; the paper notes that the latter problem is believed to be hard on average near the maximum-clique threshold, while the proposed reduction remains unproved.