Tesis doctoral


La defensa tendrá lugar el 28 de noviembre de 2019. Más detalles debajo.


Condition and Homology in Semialgebraic Geometry

(Condición y Homología en Geometría Semialgebraica)



Portada de Conditionand Homology in Semialgebraic Geometry por Josué Tonelli Cueto
Josué Tonelli Cueto sosteniendo una copia de su tesis doctoral

Resumen

El cálculo de los grupos de homología de conjuntos semialgebraicos (dados por fórmulas booleanas) es todavía uno de los mayores desafíos de la geometría semialgebraica computacional. Aunque se busca un algoritmo que tome a lo sumo tiempo simplemente exponencial en el número de variables, hasta el día de hoy todos los algoritmos existentes son simbólicos y doblemente exponenciales. En esta tesis doctoral, mostramos cómo se puede obtener un algoritmo numérico que tome tiempo simplemente exponencial con alta probabilidad, lo cual es una mejora del estado del arte. Para ello, explicamos las ideas, métodos y técnicas subyacentes procedentes de la geometría algebraica numérica, de la complejidad numérica y del análisis topológico de datos que han hecho posible este progreso. Terminamos con una lista de problemas y preguntas abiertas que indican un posible futuro de la computación numérica de invariantes topológicos.

Además, en los apéndices, estudiamos el número esperado de ceros reales de un sistema oligonómico aleatorio y damos una visión informal del tema principal de esta tesis en castellano.

Laburpena (Resumen en euskera)

Multzo semialjebraikoen (formula boolearrek emandakoen) homologia-taldeak kalkulatzeak jarraitzen du, oraindik ere, geometria semialjebraiko konputazionalaren erronka handienetako bat izaten. Bilatzen den algoritmoak aldagai kopuruan baino ez du hartzen denbora behin esponentziala; hala ere, gaur egun dauden algoritmo guztiak sinbolikoak eta bi aldiz esponentzialak dira. Doktorego-tesi honetan erakusten dugu nola lor daitekeen debora behin esponentzialean eta probabilitate handiarekin exekutatzen den zenbakizko algoritmo bat; hori teknikaren egoeraren hobekuntza da. Horretarako, zenbakizko geometria aljebraikoaren, zenbakizko konplexutasunaren eta datu-analisi topologikoaren azpian dauden eta aurrerapen hori posible egin duten ideia, metodo eta teknikak azaltzen ditugu. Problemen eta galdera irekien zerrenda batekin bukatzen dugu, zeinek inbariante topologikoen zenbakizko konputazioaren etorkizun posible bat adierazten baitute.

Gainera, eranskinetan, ausazko sistema oligonomiko baten zero kopurua aztertzen dugu, eta tesi honen ikuspegi informala ematen dugu gaztelaniaz.

Abstract (Resumen en inglés)

The computation of the homology groups of semialgebraic sets (given by Boolean formulas) remains one of the open challenges of computational semialgebraic geometry. Despite the search for an algorithm taking singly exponential time only on the number of variables, as of today, the existing algorithms are symbolic and doubly exponential. In this PhD thesis, we show how to obtain a numerical algorithm running in single exponential time with very high probability, which improves the state-of-the-art. To do so, we explain the underlying ideas, methods and techniques from numerical algebraic geometry, numerical complexity and topological data analysis that made this progress possible. We finish with a list of open problems and questions pointing to a possible future of the numerical computation of topological invariants.

Additionally, in the appendices, we cover the topic of the expected number of real zeros of a random fewnomial system and we give an accessible account of the central theme in Spanish.

Zusammenfassung (Resumen en alemán)

Die Berechnung der Homologiegruppen von semialgebraichen Mengen (gegeben durch boolesche Formeln) bleibt eine der offenen Herausforderungen der algorithmischen semialgebraischen Geometrie. Trotz der Suche nach einem Algorithmus mit einfach exponentieller Laufzeit in der Anzahl der Variablen, sind die nach heutigem Stand bekannten Algorithmen symbolisch und doppelt exponentiell. In dieser Doktorarbeit zeigen wir, wie man einen numerischen Algorithmus konstruiert, der mit großer Wahrscheinlichkeit einfach exponentiell ist und somit den Stand der Forschung verbessert. Dazu erklären wir die zugrundliegenden Ideen, Methoden und Techniken von numerischer algebraischen Geometrie, numerischer Komplexität und topologischer Datenanalyse, die dieser Fortschrift möglich machten. Wir enden mit einer Liste offener Probleme und Fragen, die auf eine mögliche Zukunft von Berechnung der topologischen Invarianten weisen.

Außerdem, behandeln wir im Anhange die erwartete Anzahl reeller Nullstellen eines zufälligen Systems polynomialer Gleichungen mit wenigen Termen und geben einen informellen Überblick über das Hauptthema auf Spanisch.


Tesis doctoral

La tesis doctoral fue entregada el 11 de octubre de 2019. Esta está actualmente bajo examiación por los evaluadures Peter Bürgisser, Felipe Cucker y Pierre Lairez.


Defensa doctoral

La defensa doctoral está planeada para el 28 de noviembre de 2019 a las 12:00. La defensa tendrá lugar en el aula MA313/314 en la 3ª planta del Institut für Mathematik de la Technische Universität Berlin (Str. des 17. Juni 136). El comité de la defensa doctoral será presidido por John M. Sullivan y estará compuesto por los evaluadores Peter Bürgisser, Felipe Cucker and Pierre Lairez. Después de la defensa, habrá una pequeña celebración con comida y bebidas en el Matheon Lounge (MA315).