English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

A seminal work of Jerrum (1992) showed that large cliques elude theMetropolis process. More specifically, Jerrum showed that the Metropolisalgorithm cannot find a clique of size $k=\Theta(n^{\alpha}), \alpha \in(0,1/2)$, which is planted in the Erd\H{o}s-R\'{e}nyi random graph $G(n,1/2)$,in polynomial time. Information theoretically it is possible to find suchplanted cliques as soon as $k \ge (2+\epsilon) \log n$.  Since the work of Jerrum, the computational problem of finding a plantedclique in $G(n,1/2)$ was studied extensively and many polynomial timealgorithms were shown to find the planted clique if it is of size $k =\Omega(\sqrt{n})$, while no polynomial-time algorithm is known to work when$k=o(\sqrt{n})$. Notably, the first evidence of the problem's algorithmichardness is commonly attributed to the result of Jerrum from 1992.  In this paper we revisit the original Metropolis algorithm suggested byJerrum. Interestingly, we find that the Metropolis algorithm actually fails torecover a planted clique of size $k=\Theta(n^{\alpha})$ for any constant $0\leq \alpha < 1$.  Moreover, we strengthen Jerrum's results in a number of other ways including:Like many results in the MCMC literature, the result of Jerrum shows that thereexists a starting state (which may depend on the instance) for which theMetropolis algorithm fails. For a wide range of temperatures, we show that thealgorithm fails when started at the most natural initial state, which is theempty clique. This answers an open problem stated in Jerrum (1992). We alsoshow that the simulated tempering version of the Metropolis algorithm, a moresophisticated temperature-exchange variant of it, also fails at the same regimeof parameters.  Finally, our results confirm recent predictions by Gamarnik and Zadik (2019)and Angelini, Fachin, de Feo (2021).

Almost-Linear Planted Cliques Elude the Metropolis Process