| Tuesday, March 12th, 2013 | 4pm-5pm | Burnside 1205 |
To deal with NP-hard reconstruction problems, one natural possibility consists in assuming that the input data is a noisy version of some unknown ground truth. We present several examples, in particular correlation clustering, and transitive tournaments. In correlation clustering, the goal is to partition data given pairwise similarity and dissimilarity information, and sometimes semi-definite programming can, with high probability, reconstruct the optimal (maximum likelihood) underlying clustering. The proof uses semi-definite programming duality and the properties of eigenvalues of random matrices. The transitive tournament problem asks to reverse the fewest edge orientations to make an input tournament transitive. In the noisy setting it is possible to reconstruct the underlying ordering with high probability using simple dynamic programming.