The theoretical information threshold for the planted clique problem is 2 log(2) (N), but no polynomial algorithm is known to recover a planted clique of size O(N1/ 2-epsilon), epsilon > 0. In this paper we will apply a standard method for the analysis of disordered models, the parallel tempering (PT) algorithm, to the clique problem, showing numerically that its time-scaling in the hard region is indeed polynomial for the analyzed sizes. We also apply PT to a different but connected model, the sparse planted independent set problem. In this situation thresholds should be sharper and finite size corrections should be less important. Also in this case PT shows a polynomial scaling in the hard region for the recovery.
Parallel tempering for the planted clique problem / Angelini, Maria Chiara. - In: JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT. - ISSN 1742-5468. - 2018:7(2018), p. 073404. [10.1088/1742-5468/aace2c]
Parallel tempering for the planted clique problem
Maria Chiara, Angelini
Primo
2018
Abstract
The theoretical information threshold for the planted clique problem is 2 log(2) (N), but no polynomial algorithm is known to recover a planted clique of size O(N1/ 2-epsilon), epsilon > 0. In this paper we will apply a standard method for the analysis of disordered models, the parallel tempering (PT) algorithm, to the clique problem, showing numerically that its time-scaling in the hard region is indeed polynomial for the analyzed sizes. We also apply PT to a different but connected model, the sparse planted independent set problem. In this situation thresholds should be sharper and finite size corrections should be less important. Also in this case PT shows a polynomial scaling in the hard region for the recovery.File | Dimensione | Formato | |
---|---|---|---|
Angelini_Parallel_2018.pdf
solo gestori archivio
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
1.04 MB
Formato
Adobe PDF
|
1.04 MB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.