Given either a random d-regular graph or a random k-colorable d-regular graph, for what values of k is there an efficient algorithm to distinguish between the two distributions? Heuristics based on statistical physics predict that k should be at most sqrt{d-1}. We give algorithms to solve the distinguishing problem arbitrarily close to the predicted threshold and additionally show that these satisfy certain robustness guarantees, i.e. they still correctly solve the distinguishing problem after a small number of adversarial perturbations.

This talk is based on joint work with Jess Banks and Prasad Raghavendra.