Ayant déjà parlé récemment de mes travaux de recherche dans un séminaire de l’équipe de géométrie, je propose, de les représenter en mettant plus l’accent sur mes travaux en complexité arithmétique. La question du temps de calcul nécessaire à l’évaluation des polynômes naturels semble fondamentale. Ainsi, quelle est la meilleure façon de calculer un polynôme f(X_1,…,X_n) à partir des opérations arithmétiques basiques + et *? En fait, certains polynômes sont difficiles à calculer. Par exemple, évaluer le permanent d'une matrice revient à compter le nombre de mariages parfaits dans un graphe. On commencera par une présentation de pistes de recherche actuelles en complexité arithmétique. Puis, on verra comment paralléliser ces calculs de manière efficace. Je présenterai mes derniers résultats : en particulier, je montrerai comment obtenir des bornes inférieures ``presque''-cubiques (et ainsi battre les bornes précédentes quadratiques) sur la taille des circuits arithmétiques de profondeur 3 calculant un polynôme donné. Enfin, je comptais juste montrer comment des conjectures de géométrie algébrique réelle impliquent des bornes inférieures non triviales pour le temps de calcul.
We study a generalization of beta expansion to 2 dimension involving rotation action. Basic questions are its ergodicity and soficness. In particular, sofic cases give rise to a large class of self-similar polygonal tilings, having 2n-th fold (diffractive) symmetry for any n. This is a joint work with Jonathan Caalim.
Dans cet exposé, nous commencerons par définir les invariants motiviques à l'infini d'un polynôme. Nous étudierons ensuite le cas d'un polynôme à deux variables et à coefficients complexes. Les calculs seront donnés en termes des polygones de Newton du polynôme. Lorsque le polynôme est non dégénéré pour son polygone de Newton, le calcul est aisé, dans le cas contraire,nous proposons un raisonnement par induction utilisant des transformations de Newton et des polygones itérés à hauteur décroissante. Travail en commun avec Pierrette Cassou-Nogues (Bordeaux)
Je présenterai une nouvelle sémantique de réalisabilité du lambda-mu-calcul simplement typé et je montrerai un résultat de correction pour la valider. Je donnerai ensuite un modèle particulier de ce calcul qui permettra de prouver la complétude. Je finirai par quelques conséquences de ce résultat ainsi que quelques questions ouvertes.
La méthode des points vortex est une approche théorique et numérique couramment utilisée afin d'implémenter le mouvement d'un fluide parfait (en dimension deux), dans laquelle le tourbillon est approché par une somme de points vortex, de sorte que les équations d'Euler se réécrivent comme un système d'équations différentielles ordinaires. Une telle méthode n'est rigoureusement justifiée que dans le plan complet, grâce aux formules explicites de Biot-Savart. Dans un domaine extérieur, nous remplaçons également le bord imperméable par une collection de points vortex, générant une circulation autour de l'obstacle. La densité de ces points est choisie de sorte que le flot demeure tangent au bord sur certains points intermédiaires aux paires de tourbillons adjacents sur le bord. Dans cet exposé, nous proposons une justification rigoureuse de cette méthode dans des domaines extérieurs. L'une des principales difficultés mathématiques étant que le noyau de Biot-Savart définit un opérateur intégral singulier lorsqu'il est restreint à une courbe. Ce travail est en collaboration avec D. Arsénio (Paris Diderot) et E. Dormy (ENS Paris).
In the context of chemical reaction networks with mass-action and other rational kinetics, a major question is to preclude or to guarantee multiple positive steady states. I will explain this motivation and I will present necessary and sufficient conditions in terms of sign vectors for the injectivity of families of polynomials maps with arbitrary real exponents defined on the positive orthant. These conditions extend existing injectivity conditions expressed in terms of Jacobian matrices and determinants, obtained by several authors. In the context of real algebraic geometry, this approach can be seen as the first partial multivariate generalization of the classical Descartes' rule, which bounds the number of positive real roots of a univariate real polynomial in terms of the number of sign variations of its coefficients. This is joint work with Stefan Müller, Elisenda Feliu, Georg Regensburger, Anne Shiu and Carsten Conradi. I will also present some further advances in this multivariate generalization obtained in collaboration with Frédéric Bihan, together with applications to biochemical MESSI systems obtained in collaboration with Mercedes Pérez Millán.
We revisit coinductive proof principles from a lattice theoretic point of view. By associating to any monotone function a function which we call the companion, we give a new presentation of both Knaster-Tarski's seminal result, and of the more recent theory of enhancements of the coinductive proof method (up-to techniques). The resulting theory encompasses parametrised coinduction, as recently proposed by Hur et al., and second-order reasoning, i.e., the ability to reason coinductively about the enhancements themselves. It moreover resolves an historical peculiarity about up-to context techniques. Based on these results, we present an open-ended proof system allowing one to perform proofs on-the-fly and to neatly separate inductive and coinductive phases.
Nous montrons la stabilité sous intégration et transformation de Fourier d’une algèbre explicite de fonctions contenant les fonctions sous-analytiques et leurs exponentielles complexes. Il s'agit d'un article en commun avec R. Cluckers, D. Miller, J. P. Rolin & T. Servi.
On va montrer comment programmer sur des streams avec l'axiome de l'ultrafiltre, qui en quelque sorte correspond à une forme limitée de programmation concurrente pour calculer un stream infini.
An inequality by P'olya establishes that the product between the torsional rigidity and the first Dirichlet Laplacian eigenvalue is bounded from above in the class of bounded sets with given measure. We investigate the sharpness of the constant appearing in P'olya's inequality and we try to improve it in a suitable class of sets. This is a joint work with M. van den Berg, V. Ferone and C. Nitsch.
A tout mot infini w uniquement ergodique, considéré comme un élément d'un sous-shift, nous associons un nombre réel nu(w) entre 0 et 1 égal à la mesure de l'ensemble des mots inférieurs ou égal à w. Lopez et Narbel ont montré (2016) que si la complexité du mot est assez basse, le décalage de mots correspond à un échange d'intervalles pour ces nombres associés. Nous montrons que si le mot w est un point fixe d'un ``bon'' morphisme, et en particulier d'un morphisme binaire, alors nu(w) et les valeurs de nu pour tous les décalages de w peuvent être trouvés à l'aide d'un morphisme sur les nombres réels.
En tant que nouvel arrivant au laboratoire, je voudrais présenter lors de cet exposé des questions, des sujets de recherche qui m'intéressent. La question du temps nécessaire algorithmiquement pour l'évaluation de polynômes naturels semble fondamentale. Quelle est la meilleure façon de calculer un polynôme f(X_1,…,X_n) à partir des opérations arithmétiques basiques + et *? En fait, certains polynômes sont difficiles à calculer. Par exemple, évaluer le permanent d'une matrice revient à compter le nombre de mariages parfaits dans un graphe. Une autre façon de voir ce problème est celui de la possibilité d'exprimer le permanent comme déterminant d'une matrice, une question déjà soulevée par Pólya et Szegö en 1913. On commencera par une présentation de pistes de recherche actuelles en complexité arithmétique. On verra des relations avec des questions de géométrie algébrique (en particulier, en géométrie réelle) et les questions qui apparaissent - ou plutôt ressurgissent - dans ce domaine. Ainsi, de nombreuses propriétés des variétés réelles définies par des courbes creuses sont encore très mal connues. Je finirai par présenter mes derniers résultats : en particulier, je montrerai comment obtenir des bornes inférieures ``presque''-cubiques (et ainsi battre les bornes précédentes quadratiques) sur la taille des circuits arithmétiques de profondeur 3 calculant un polynôme donné.
In this talk a development of normal form methods for special classes of partial differential equations is presented. A basic application of the methods is splitting of slow and fast wave motions and finding of equations for the slow wave motion. The rotating shallow water model is the main example for the application of the general theory. http://www.sciencedirect.com/science/article/pii/S157469090602003X
On présente dans cet exposé des méthodes de restauration d'images (inpainting) par des EDPs d'ordre deux et d'ordre quatre. L'approche adaptative permet de construire (et ajuster) les modèles proposés de manière dynamique a fin de rétablir au mieux les composantes géométriques d'une image endommagée (arêtes, coins, ...) tout en respectant les courbures. Ces méthodes consistent en une famille d'énergies discrètes, faciles à minimiser, qui $Gamma$-convergent vers des fonctionnelles de type Mumford-Shah et donnent lieu à des algortihmes efficaces.
Une nouvelle définition, implicite, du champ de gradient d'une image discrète est proposée. L'opération de différentiation qui associe une image a son champ de gradient, défini sur une grille deux fois plus fine, est non linéaire, et peut être vue comme l'inverse de l'opération (linéaire) d'intégration. Alors, la variation totale d'une image est simplement la norme l1 de l'amplitude de son champ de gradient. Cette nouvelle définition de la variation totale donne des contours nets et possède de meilleures propriétés d'isotropie que la définition classique.
TBA
We study isolated singularities of a space embedded in a smooth Riemannian manifold from a differential geometric point of view. While there is a considerable literature on bi-lipschitz invariants of singularities, we obtain a more precise (complete asymptotic) understanding of the metric properties of certain types of singularities. This involves the study of the family of geodesics emanating from the singular point. While for conical singularities this family of geodesics, and the exponential map defined by them, behaves much like in the smooth case, the situation is very different in the case of cuspidal singularities, where the exponential map may fail to be locally injective. We also study a mixed conical-cuspidal case. Our methods involve the description of the geodesic flow as a Hamiltonian system and its resolution by blow-ups in phase space. This is joint work with Vincent Grandjean.
I will present an algebraic approach to stochastic graph-rewriting. Rules are seen as particular elements of an algebra of “diagrams”: the diagram algebra D. Diagrams can be thought of as formal computational traces represented in partial time. They can be evaluated to normal diagrams (each corresponding to a rule) and generate an associative unital non-commutative algebra of rules: the rule algebra R. Evaluation becomes a morphism of unital associative algebras which maps general diagrams in D to normal ones in R. In this algebraic reformulation, usual distinctions between graph observables (real-valued maps on the set of graphs defined by counting subgraphs) and rules disappear. Actual graph-rewriting is recovered as a canonical representation of the rule algebra as linear operators over the vector space generated by (isomorphism classes of) finite graphs. This shift of point of view, away from its canonical representation to the rule algebra itself, has unexpected consequences. We find that natural variants of the evaluation morphism map give rise to concepts of graph transformations hitherto not considered. This is joint work with N. Behr and V. Danos.