Polynomial approximation: a structural and operational study

This is a summary of the most important results of the author’s PhD thesis. This thesis, supervised by Vangelis Th. Paschos, was defended in October 2005 at the Université Paris Dauphine. It is written in French and is available on-line. The thesis is focused on combinatorial optimization problems, studied from the standpoint of polynomial approximation theory. We were interested both in structural concerns (mainly completeness in approximation classes and logical expressivity) and operational ones (with the study of satisfiability, coloring and covering problems). http://www.lamsade.dauphine.fr/~escoffier/fichiers/TheseEscoffier.pdf