Complexity theory helps us predict and control resources, usually time and space, consumed by programs. Static analysis on specific syntactic criterion allows us to categorize some programs. A common approach is to observe the program’s data’s behavior. For instance, the detection of non-size-increasing programs is based on a simple principle : counting memory allocation and deallocation, particularly in loops. This way, we can detect programs which compute within a constant amount of space. This method can easily be expressed as property on control flow graphs. Because analyses on data's behaviour are syntactic, they can be done at compile time. Because they are only static, those analyses are not always computable or easily computable and approximations need are needed. Size-Change Principle'' from C. S. Lee, N. D. Jones et A. M. Ben-Amram presented a method to predict termination by observing resources evolution and a lot of research came from this theory. Until now, these implicit complexity theories were essentially applied on more or less toy languages. This thesis applies implicit computational complexity methods intoreal life'' programs by manipulating intermediate representation languages in compilers. This give an accurate idea of the actual expressivity of these analyses and show that implicit computational complexity and compilers communities can fuel each other fruitfully. As we show in this thesis, the methods developed are quite generals and open the way to several new applications.
Je vais présenter quelques nouvelles techniques pour résoudre les équations G(x,y)=0 où G(x,y)=G(x_1,...,x_n,y) est une fonction dans une classe quasi-analytique (par exemple, une classe Denjoy-Carleman quasi-analytique). Plusieurs questions importantes sur les fonctions quasi-analytiques, concernant la division, la factorisation, le lemme de préparation de Weierstrass, etc., entrent dans le cadre de ce problème. Aucune connaissance préliminaire sur les fonctions quasi-analytiques ne sera nécessaire. Je donnerai un bref panorama sur les fonctions quasi-analytiques, en mettant l’accent sur les différences avec les fonctions analytiques. Ensuite, je présenterai une technique de prolongement quasi-analytique (basée sur la résolution des singularités) et le résultat suivant (à partir d’un travail conjoint avec E. Bierstone et I. Biborski) : si G(x,y)=0 a une solution formelle y=H(x), alors H(x) est le développement de Taylor d’une solution quasi-analytique y=h(x), où h(x) a une certaine perte de régularité contrôlée par G.
We consider the linear wave equation and the linear Schrödinger equation outside a compact, strictly convex obstacle in Rd with smooth boundary. In dimension d=3 we show that the linear wave flow and the linear Schrödinger flow satisfy the dispersive estimates as in R3. For d> 3, if the obstacle is a ball, we show that there exists points where the dispersive estimates fail for both wave and Schrödinger equations.
It is well known that the motion of an incompressible fluid can be described in Eulerian variables (as a solution of a PDE, namely the continuity equation), or alternatively in Lagrangian variables (as a flow of an ODE). The classical DiPerna-Lions-Ambrosio theory ensures well-posedness and provides structural properties for solutions of the continuity equation, under suitable regularity assumptions on the velocity field and integrability assumptions on the solution. In my talk I will focus on the ``Lagrangianity'' of solutions, that is, on the property of being transported by an ODE flow, hence addressing the question whether an Eulerian solution is automatically a Lagrangian solution. After a brief summary of the DiPerna-Lions-Ambrosio theory, I will present two examples which are outside of the assumptions of such a theory, and in which nevertheless we can prove the Lagrangianity of solutions. The first one concerns vanishing viscosity solutions of the two-dimensional Euler equations, where we can use suitable duality methods (joint work with Stefano Spirito). The second example involves general continuity equations, and requires the proof of a new Lipschitz extension lemma (joint work with Laura Caravenna).
Soit c un nombre rationnel. Considérons le polynôme φ(X) = X^2 - c. On s’intéressse aux cycles de φ dans Q. Plus précisément, on s’intéresse à l’une des conjectures de Poonen selon laquelle tout cycle de φ dans Q admet une longueur au plus égale à 3. Dans notre exposé, on discutera de cette conjecture et on rappellera les résultats connus. En suite, on utilisera des moyens arithmetiques, combinatoriaux et analytiques simples pour étudier des cas particuliers de ce problème. Les outils utilisés dans cet exposé sont accessibles aux étudiants de master 2.
En utilisant le travail de Guillén et Navarro Aznar sur les hyperrésolutions cubiques, Totaro a introduit un analogue de la filtration par le poids de Deligne sur l'homologie et la cohomologie des variétés algébriques réelles, fonctorielle, triviale sur les variétés lisses compactes, additive et compatible avec les résolutions des singularités. McCrory et Parusinski ont montré que la filtration par le poids réelle homologique et ses propriétés étaient induites par un complexe de chaînes filtré géométrique, appelé filtration géométrique. Un article avec Limoges montre également que le dual de ce dernier induit la filtration par le poids réelle cohomologique, et que ces filtrations géométriques induisent la compatibilité des filtrations par le poids réelles avec les produits usuels (cartésiens, cup, cap). Si l'on considère maintenant des variétés algébriques réelles munies de l'action d'un groupe fini, la fonctorialité des filtrations géométriques permet d'induire une filtration par le poids sur des homologie et cohomologie équivariantes, définies par van Hamel pour vérifier une dualité de Poincaré sur les variétés topologiques avec action. Des différences significatives apparaissent cependant entre les filtrations par le poids réelles équivariantes et non-équivariantes. Dans cet exposé, on verra comment la fonctorialité des complexes filtrés géométriques induit néanmoins la compatibilité des filtrations par le poids équivariantes réelles avec les produits cartésiens, cup et cap équivariants, ainsi qu'avec le morphisme de dualité de Poincaré équivariant.
Dans cette exposé, on montre comment donner une interprétation géométrique et dynamique à certains algorithmes de fraction continues multidimensionnelles; cela permet, en utilisant l'algorithme de Brun, de donner un modèle symbolique pour le flot des chambres de Weil.
Dans cet expose je m'interesserai a la resolution du probleme de Stokes stationnaire dans un domaine perfore avec des conditions aux bords de type Dirichlet inhomogene. Je discuterai la possibilite de developper la solution sur cette geometrie complexe comme une somme de solution dans des geometries plus simples (obtenues en considerant les perforations independamment). Je m'interesserai ensuite a l'application de ces formules pour calculer une equation homogeneisee quand le nombre de perforations diverge alors que leurs rayons tendent vers 0. Cet expose s'appuie sur des resultats obtenus en collaboration avec Amina Mecherbet, Ayman Moussa et Franck Sueur.
La théorie du micromagnétisme, qui décrit l'aimantation des matériaux ferromagnétiques à l’échelle mésoscopique a fait l'objet d'études approfondies depuis sa construction dans les années 1940 par W. F. Brown et Landau-Lifshitz. Actuellement, une forte demande de la part d’une large communauté de physiciens et d'ingénieurs concerne l’obtention de modèles encore plus complexes et stochastiques (spatiaux et temporels). L’utilisation de structures aléatoires spatiales est en effet naturelle pour les aimants modernes, obtenus par alliage de plusieurs matériaux ayant des propriétés magnétiques différentes. Nous étudierons l’homogénéisation de ces matériaux, décrits par les équations de Landau-Lifshitz avec des coefficients aléatoires.
Motivated by mirror symmetry, we study the counting of open curves in log Calabi-Yau surfaces. Although we start with a complex surface, the counting is achieved by applying methods from Berkovich geometry (non-archimedean analytic geometry). This gives rise to new geometric invariants inaccessible by classical methods. These invariants satisfy a list of very nice properties and can be computed explicitly. I will mention the conjectural wall-crossing formula, relations with the works of Gross-Hacking-Keel and applications towards mirror symmetry.
Groupe de travail : Fonctions Zêta, Théorie des Nombres, Géométrie
Nous présentons ici deux techniques, parfois concordantes, de stabilisation de schémas numériques semi-implicites pour les problèmes paraboliques non-linéaires. Les schémas proposés sont appliqués d'une part, en différences finies, lorsque les opérateurs sont discrétisés à l'aide de schémas compacts et, d'autre part, en éléments finis enutilisant une approche bi-grilles. Nous illustrons notre propos en considérant des modèles de champ de phase (Cahn-Hilliard et Allen -Cahn) et de mécanique des fluides (Navier-Stokes).
La logique linéaire différentielle (DiLL) a été construite après une étude de modèles vectoriels de la logique linéaire, où les preuves sont interprétées par des séries plus ou moins formelles. Il s'agit donc de modèles discrets, où la différentielle extrait la partie linéaire d'une série entière. On cherche à trouver un modèle continu de la logique linéaire différentielle classique : il nous faut à la fois une catégorie cartésienne close de fonctions lisses et une catégorie monoidale close d'espaces réfléxifs. Nous allons détailler une solution partielle à ce problème, à travers d'espaces nucléaires et d'espaces de distributions. Nous verrons comment ce modèle suggère une syntaxe séparée en classes de formules, chaque classe correspondant aux solutions d'une EDP linéaire. Nous montrerons que chaque classe liée à une EDP dont on peut construire la solution se comporte comme une exponentielle intermédiaire, et vérifie les règles exponentielles de la logique linéaire différentielle. Si le temps le permet, nous aborderons un travail en collaboration avec Y. Dabrowski , où nous trouvons plusieurs modèles lisses de la logique linéaire différentielle, en faisant le choix discriminant d'interpréter la disjonction multiplicative de LL par le produit epsilon de Schwartz.
Afin d'étudier les propriétés arithmétiques d'une fonction entière, Coman et Poletsky ont introduit une notion de mesure de transcendance. Cette mesure joue un rôle similaire aux mesures de transcendances en approximation diophantienne. Par la suite ils ont obtenu une majoration de cette mesure de transcendance sous des conditions de distribution des petites valeurs de la fonction entière étudiée. J'expliquerai comment cette mesure de transcendance peut être étendue aux fonctions méromorphes sur le disque unité ou le plan. De façon analogue à la situation entière, il sera possible de majorer cette mesure sous des conditions de distribution des petites valeurs de la fonction méromorphe et des pôles de celle-ci. J'appliquerai ce résultat au cas des fonctions elliptiques et fuchsiennes. Enfin j'expliquerai le lien entre les lemmes de zéros et les mesures de transcendances de cet exposé.
In the first part of this talk, I'll recall the construction of category of games and innocent deterministic strategies introduced by Harmer, Hyland and Mellies [1]. Compared with the original method by Hyland and Ong [2], this method holds two specific advantages. First, it outlines the structural conditions on certain games and strategies by introducing separate entities (the schedules) that focus most of the required proof work. Second, the methods lays out a pretty clear combinatorial ‘recipe’ that could be replicated in other settings. That will be the goal of the second part of the talk, which will develop a 2-categorical and sheaf-theoretic formulation of non-deterministic innocent strategies, based on this ‘recipe’. During the course of this construction, I'll outline specific properties that give us a better understanding of both deterministic and non-deterministic strategies.
[1] Categorical combinatorics of innocent strategies, Harmer, Hyland, Mellies, LiCS 2007.
[2] On full abstraction for PCF I, II and III, Hyland, Ong, Information and Computation 2000.
The aim of the talk is to provide a concise survey of some results about variational methods for image segmentation and inpainting, in the framework of functions of Special Bounded Variation in the sense of De Giorgi.
The lambda-calculus possesses a strong notion of extensionality, called ``the omega-rule'', which has been the subject of many investigations. It is a longstanding open problem whether the equivalence obtained by closing the theory of Böhm trees under the omega-rule is strictly included in Morris's original observational theory, as conjectured by Sallé in the seventies. We will first show that Morris's theory satisfies the omega-rule. We will then demonstrate that the two aforementioned theories actually coincide, thus disproving Sallé's conjecture.
The proof technique we develop is general enough to provide as a byproduct a new characterization, based on bounded eta-expansions, of the least extensional equality between Böhm trees.