Many problems in random combinatorial structures exhibit an apparent gap between the existential results and algorithmically achievable results, though no formal complexity theoretic hardness of these problems is known. Examples include the problem of proper coloring of a random graph, finding a largest independent set of a graph, random K-SAT problem, and many others. In our talk we consider a new example of such a gap for the problem of finding a  submatrix which achieves the largest average value in a given random matrix. We will consider some known and a new algorithm for this problem, all of which produce a matrix with average value constant factor away from the globally optimal one. We then consider the overlap structure of pairs of matrices achieving a certain average value, and show that it undergoes a certain  connectivity phase transition just above the value achievable by the best known algorithm. We conjecture that the onset of this overlap gap property marks the onset of the algorithmic hardness for this problem and in fact we conjecture that this is the case for most randomly generated optimization problems.

 

Joint work with Quan Li (MIT)