Mikkel Thorup (Basic Algorithms Research Center, Copenhagen)
Reconstructing the Tree of Life (Fitting Distances by Tree Metrics) abstract
Abstract:
We consider the numerical taxonomy problem of fitting an SxS distance matrix D with a tree metric T. For some k, we want to minimize the L_k norm of the errors, that is,
Pick T so as to minimize (sum_{i,j in S} |D(i,j)-T(i,j)|^k)^{1/k}
This problem was raised in biology in the 1960s for k=1,2. The biological interpretation is that T represents a possible evolution behind the species in S matching some measured distances in D. Sometimes, it is required that T is an ultrametric, meaning that all species are at the same distance from the root.
An Evolutionary tree induces a hierarchical classification of species and this is not just tied to biology. Medicine, ecology and linguistics are just some of the fields where this concept appears, and it is even an integral part of machine learning and data science. Fundamentally, if we can approximate distances with a tree, then they are much easier to reason about: many questions that are NP-hard for general metrics can be answered in linear time on tree metrics. In fact, humans have appreciated hierarchical classifications at least since Plato and Aristotle (350 BC).
We will review the basic results on the problem, including the most recent result from FOCS\'21 https://arxiv.org/abs/2110.02807. They paint a varied landscape with big differences between different moments, and with some very nice open problems remaining.
At STOC\'93, Farach, Kannan, and Warnow proved that under L_infty, we can find the optimal ultrametric. Almost all other variants of the problem are APX-hard.
At SODA\'96, Agarwala, Bafna, Farach, Paterson, and Thorup showed that for any norm L_k, k>=1, if the best ultrametric can be A-approximated, then the best tree metric can be 3A-approximated. In particular, this implied a 3-approximation for tree metrics under L_infty.
At FOCS\'05, Ailon and Charikar showed that for any L_k, k>=1, we can get an O(((log n)(loglog n))^{1/k}) approximation for both tree and ultrametrics. Their paper was focused on the L_1 norm, and they wrote ``Determining whether an O(1) approximation can be obtained is a fascinating question".
At FOCS\'21, Cohen-Addad, Das, Kipouridis, Parotsidis, and Thorup showed that indeed a constant factor is possible for L_1 for both tree and ultrametrics. This uses the special structure of L_1 in relation to hierarchies.
The status of L_k is open for 1.
Joint work with Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis and Nikos Parotsidis.
10:15 • EPF Lausanne, room GA 3 21
Weronika Czerniawska (Université de Genève)
Tate\'s global harmonic analysis and the uniform approach to the Riemann-Roch theorem in dimension one abstract
Abstract:
In my talk, I will explain how to extend the approach to Riemann-Roch theorem from Tate\'s thesis to the relative case (i.e. the case of morphism between curves) for both arithmetic and geometric case.
14:15 • Universität Basel, Spiegelgasse 5, SR 05.002
Marco Volpe (Universität Regensburg)
Verdier duality on conically smooth stratified spaces abstract
Abstract:
Verdier duality is a key feature of derived categories of constructible sheaves on well-behaved stratified spaces. In this talk we will explain how to extend the duality theorem to constructible sheaves on conically smooth stratified spaces and with values in a general stable bicomplete infinity-category. Our proof relies on two main ingredients, one categorical and one geometric. The first one is an equivalence between sheaves and cosheaves proven by Lurie in Higher Algebra. Lurie\'s theorem will appear in our discussion both as a fundamental building block for the six functor formalism in a very general setting and as a factor of the duality functor on constructible sheaves. The second is the unzip construction introduced by Ayala, Francis and Tanaka, which provides a functorial resolution of singularities to smooth manifolds with corners. This will be used to prove that the exit path infinity-category of any compact conically smooth stratified space is finite.
15:15 • ETH Zentrum, Rämistrasse 101, Zürich, Building HG, Room G 43
Prof. Dr. Melanie Rupflin (University of Oxford)
Abstract:
Many interesting geometric objects are characterised as minimisers or critical points of natural geometric quantities such as the length of a curve, the area of a surface or the energy of a map. For the corresponding variational problems it is often important to not only analyse the existence and properties of potential minimisers, but to obtain a more general understanding of the energy landscape.
It is for example natural to ask whether an object that has energy very close to the minimal possible energy must also essentially "look like" a minimiser, and if so whether this holds in a quantitative sense, i.e. whether one can bound the distance to a minimiser in terms of the energy defect. Similarly one would like to understand whether for points where the gradient of the energy is very small one can hope to bound the distance of this point to the set of critical points in terms of the size of the gradient.
In this talk we will discuss some aspects of such quantitative estimates for geometric variational problems and their role in understanding the dynamics of the associated gradient flows
17:00 • UniDistance Suisse, Zoom Seminar
Alexandra Florea (University of California Irvine)
Abstract:
I will talk about work towards a conjecture of Gonek regarding negative shifted moments of the Riemann zeta function. I will explain how to obtain asymptotic formulas when the shift in the Riemann zeta function is big enough, and how one can obtain non-trivial upper bounds for smaller shifts. Joint work with H. Bui.
17:00 • Universität Basel, online Seminar
Dr. Stephan Tobias Eckstein (ETH Zürich, Switzerland)
Causal optimal transport with general information structures abstract
Abstract:
We present a framework of optimal transport aimed at probability measures arising from structural causal models, i.e., models that contain an information structure dictated by a directed graph. This builds on the recent string of literature (called causal or adapted optimal transport) studying this concept for time-series distributions, which has found many applications in financial contexts. We recover the adapted optimal transport problem for a particular temporal graph structure, and additionally show that other special cases like the standard optimal transport problem (fully connected graph) or problems related to Gromov-Wasserstein (graph without edges) are also included in the setting. The concept of coupling for a particular graph structure is characterized in various ways, giving rise to different interpretations and numerical possibilities. Further, we show that the resulting concept of Wasserstein distance can be used to control the difference between average treatment effects under different distributions, and is geometrically suitable to interpolate between different structural causal models.
17:15 • ETH Zentrum, Rämistrasse 101, Zürich, Building HG, Room G 43