In this talk, I will start by briefly presenting myself and my research topics. Then, I will introduce combinatorial optimization problems with a focus on my last publication in collaboration with Scott Kirkpatrick about Maximum Clique Problem. Finding a Maximum Clique is a classic property test from graph theory; find any one of the largest complete subgraphs in an Erdös-Rényi G(N, p) random graph.
We use Maximum Clique to explore the structure of the problem as a function of N, the graph size, and K, the clique size sought.
This displays a complex phase boundary, a staircase of steps at each of which 2 log2 N and Kmax, the maximum size of a clique that can be found, increases by 1. Each of its boundaries has a finite width, and these widths allow local algorithms to find cliques beyond the limits defined by the study of infinite systems.
We explore the performance of a number of extensions of traditional fast local algorithms, and find that much of the “hard” space remains accessible at finite N. The “hidden clique” problem embeds a clique somewhat larger than those which occur naturally in a G(N, p) random graph. Since such a clique is unique, we find that local searches which stop early, once evidence for the hidden clique is found, may outperform the best message passing or spectral algorithms.
