Titre original :
On Monotonicity Testing and the 2-to-2 Games Conjecture
Contenu du livre :
Ce livre traite de deux questions en théorie de la complexité : le problème du test de monotonicité et la conjecture des jeux 2 à 2.
Le test de monotonicité est un problème du domaine des tests de propriétés, examiné pour la première fois par Goldreich et al. en 2000. L'entrée de l'algorithme est une fonction, et le but est de concevoir un testeur qui fait le moins de requêtes possible à la fonction, accepte les fonctions monotones et rejette les fonctions loin d'être monotones avec une probabilité proche de 1.
Le premier résultat de ce livre est un algorithme essentiellement optimal pour ce problème. L'analyse de l'algorithme s'appuie fortement sur un analogue nouveau, dirigé et robuste d'une inégalité isopérimétrique booléenne de Talagrand datant de 1993.
Le théorème des preuves vérifiables de manière probabiliste (PCP) est l'une des pierres angulaires de l'informatique théorique moderne. L'un des domaines dans lesquels les PCP sont essentiels est celui de la dureté de l'approximation. L'objectif est de prouver que certains problèmes d'optimisation sont difficiles à résoudre, même approximativement. De nombreux résultats de dureté d'approximation ont été prouvés à l'aide du théorème PCP ; cependant, pour certains problèmes, des résultats optimaux n'ont pas été obtenus. Ce livre aborde certains de ces problèmes, et en particulier le problème des jeux 2 à 2 et le problème de la couverture des sommets.
Le deuxième résultat de ce livre est une preuve de la conjecture des jeux 2 à 2 (avec une complétude imparfaite), qui implique de nouveaux résultats de dureté d'approximation pour des problèmes tels que la couverture de sommets et l'ensemble indépendant. Elle constitue également une preuve solide de la conjecture des jeux uniques, un problème ouvert connexe notoire en informatique théorique. Au cœur de la preuve se trouve une caractérisation des petits ensembles de sommets dans les graphes de Grassmann dont l'expansion des arêtes est limitée à 1.
Autres informations sur le livre :
| ISBN : | 9781450399661 |
| Auteur : | |
| Éditeur : | |
| Langue : | anglais |
| Reliure : | Broché |
Achat:
Actuellement disponible, en stock.
