Fisica statistica

Revisiting the challenges of MaxClique

by Scott Kirkpatrick (Hebrew University of Jerusalem)

Europe/Rome
Aula Careri (Dipartimento di Fisica - Ed.G Marconi)

Aula Careri

Dipartimento di Fisica - Ed.G Marconi

Description
Finding the largest completely connected subgraph in a random graph has always been an attractive problem because the "hard" regime, between solutions which are found by easy local search methods, and the upper limits of solutions known to exist but not easily discovered is large. The challenge of solving this problem is usually posed in asymptotic terms, yet at the scales typical of modern big data this kind of search is in a finite-sized regime, with much interesting structure. We have studied both simple and exotic approaches for discovering both naturally occurring and "planted" solutions, using spectral and belief propagation methods, as well as greedy local search...
Organised by

Federico Ricci Tersenghi