How do you circumvent the difficulty of NP-hard optimisation problems? For all problems of the "reconstruction" type, an obvious possibility is to assume that the input data are a noisy version of an ideal reality.
Two examples of this sort of problem will be studied: clustering and transitive tournament. The clustering problem requires partition of the data which will be the most compatible with information similarity and dissimilarity between pairs of data. According to some hypotheses, semidefinite programming makes it possible to reconstruct the ideal underlying partition, with high probability. The analysis uses the duality of the semidefinite programmes and the properties of values for random patterns
The transitive tournament problem requires that data be sequenced to be most compatible with information comparing the pairs of data. According to some hypotheses, a simple dynamic programme makes it possible to reconstruct the ideal order, with high probability.
The seminar will conclude with the opportunity to put questions on topics which tend to arise in this context: satisfiability, planar graphs, etc.