Supervisor / Responsable de stage/thèse: Lenka Zdeborova, tel: +33 (0) 1 6908 8114.
Many questions of fundamental interest can be formulated as problems of statistical inference where partial or noisy observations are performed on a set of variables. The goal is to estimate the values of these variables from the indirect information contained in
the observations. Examples of such problems with large practical relevance include clustering, dictionary learning, and compressed sensing. The central scientific questions are: Under what conditions is the information contained in the measurements sufficient for a satisfactory inference to be possible? What are the most efficient algorithms for this task? To answer these questions we take advantage of the synergy between problems and settings in computer science and methods from statistical physics, such as the replica method, the cavity method and related message passing algorithms. The analysis of thresholds and phase transitions in feasibility of various inference problems leads to very fruitful ground for the development of new algorithmic ideas, and hence more efficient data processing in various application. Several concrete topics, all along the above lines, for an intership or PhD can be discussed depending on the present developement and interests of the student.