Revisiting the challenges of MaxClique
speaker: Raffaele Marino (EPFL)abstract: 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. It appears that the simplest methods still have much to contribute. The rich structure of the "hard" transition region and its boundary between possible and impossible solutions, which "concentrate" on a small number of possible answers, is seen in other common search problems. There are many incompatible paths along which to search, with no early clues as guides. Simulated annealing and approaches which locally explore a potential surface are ineffective. We hope that improving our understanding of this simple problem will contribute to other hard challenges in complex large system optimization. This is joint work with Scott Kirkpatrick.
timetable:
Wed 9 Oct, 18:20 - 18:40, Aula Dini
<< Go back