Optimalité de l’algorithme de Goemans-Williamson pour MAXCUT conditionnellement à UGC, d’après Khot, Kindler, Mossel et O’Donnell
ENS Salle RUGC + Majority is stablest => borne optimale d'inapproximabilité pour MAX-CUT
UGC + Majority is stablest => borne optimale d'inapproximabilité pour MAX-CUT
Nous généralisons les résultats classiques de Demazure dans Invariants symétriques entiers du group de Weyl et torsion aux théories cohomologiques orientées et lois de groupe formel associées quelconques. Comme exemple d'application, nous en tirons un algorithme pour calculer la structure d'anneau d'une théorie cohomologique orientée appliquée à une variété de drapeaux complets. Les groupes de Chow, le groupe de Grothendieck, la K-théorie connective, le cobordisme algébrique de Levine et Morel, etc. sont des exemples de telles théories cohomologiques.L'ingrédient principal de la construction est un anneau complet construit à partir de […]
Our motivating question is: how can one construct invariants that distinguish between the existenceof a rational point and the existence of a 0-cycle of degree 1 on some variety X. We look at thisquestion through the lens of motivic homotopy theory. Here one can use an analog of the classicalPostnikov tower to study properties of the 'S1-stable homotopy type' of a variety X. For some special X,this breaks up the homotopy type of X into pieces which can be understood as motives, and thus gives invariants which can be used […]
Preuve du principe d'invariance, version minimale utile pour Majority is Stablest
Soient K un corps et A une K-algèbre de dimension finie n. Soit r un entier satisfaisant 0 <: r
En octobre 2006, la société californienne Netflix, spécialisée dans la location de DVD, a proposé le problème suivant : partant d'un dataset (rendu public) comprenant 100 000 000 notes attribuées par 500 000 utilisateurs à 18 000 films, comment prédire efficacement les futures notes données par ces mêmes utilisateurs ? Un prix d'un million de dollars était offert à la première équipe atteignant un certain seuil de précision. La compétition, ouverte à tous, ne s'est achevée qu'à l'été 2009. Nous donnerons quelques indications sur les méthodes utilisées par les vainqueurs […]
Motivé par des problèmes de géométrie complexe, P. Milman a montré que toute solution formellement holomorphe d'un système d'équations analytique réelles peut être approchée à tout ordre par des solutions holomorphes, i.e. l'équivalent du théorème d'approximation de Artin pour ces systèmes d'équations. Néanmoins sa méthode ne permet pas d'obtenir l'existence d'une fonction d'approximation, i.e. un résultat d'approximation de Artin forte dans ce cadre. Nous allons donner une preuve de l'existence d'une telle fonction d'approximation à l'aide d'ultraproduits et de systèmes de Weierstrass à la Denef et Lipschitz en généralisant le […]
Nous montrerons d'une part, utilisant la théorie des automates finis, la décidabilité et modèle-complétude de la théorie de certains anneaux de différence (des anneaux de suites sur un corps fini) et d'autre part qu'une large classe d'anneaux de Bezout ont une théorie indécidable. Ensuite, nous considérons ces anneaux de différence comme modules sur un anneau de polynômes gauches et nous montrerons des resultats de décidabilité.Enfin, nous enrichirons ce langage de modules par une valuation et grâce a un résultat d'élimination des quantificateurs nous montrerons notamment que le corps valué des […]
Finding and searching for algebras of real or complex valued functions which are stable under parameterized integration has become a personal passion. In the p-adic, uniformly p-adic, and motivic settings, several such algebras are known (including or not additive characters), We will present joint work with Daniel Miller in which we prove the stability under Lebesgue integration of sums of products of globally subanalytic functions and their logarithms, see arXiv:0911.4373. This relates among other things to periods as presented by Kontsevich and Zagier and builds further on work by Comte, […]
Premier exposé sur les travaux de Prasad Raghavendra