Fisica statistica

Revisiting the challenges of MaxClique

by Scott Kirkpatrick (Hebrew University of Jerusalem)

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

Aula Careri

Dipartimento di Fisica - Ed.G Marconi

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...
Organized by

Federico Ricci Tersenghi

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now