Thèse Instance Dependent Prophet Inequalities And More H/F - Doctorat.Gouv.Fr

Établissement : Institut Polytechnique de Paris École nationale de la statistique et de l'administration économique École doctorale : Mathématiques Hadamard Laboratoire de recherche : CREST - Centre de recherche en économie et statistique Direction de la thèse : Vianney PERCHET ORCID 000000029333264X Début de la thèse : 2026-10-01 Date limite de candidature : 2026-06-30T23:59:59 This project aims to establish the theory and to design and study algorithms for decision-making processes that integrate AI-generated predictions into classical algorithms, ensuring they are more powerful when predictions are accurate and provably reliable when predictions are poor. Rather than motivating this by revisiting the limitations of end-to-end AI systems (as outlined before), we focus on what this integration requires in practice and how we will evaluate success.

From this perspective, the objective is to Go beyond worst-case analysis: This contrasts sharply with the traditional competitive analysis literature [3], which focuses on identifying worst-case instances and designing algorithms that perform well even under such conditions. Instead, we advocate for the development of instance-dependent complexity measures, so that algorithmic performance reflects the actual difficulty of the instance. Prophet Inequality

Maths
CS