Physique mathématique | EPFL Graph Search

La physique mathématique est un domaine de recherche commun à la physique et aux mathématiques s'intéressant au développement des méthodes mathématiques spécifiques aux problèmes physiques ou plus généralement à l'application des mathématiques à la physique, et, à l'opposé, aux développements mathématiques que suscitent certains domaines de recherche en physique. Elle inclut notamment l'étude des systèmes dynamiques, des algèbres aux symétries particulières, des méthodes de décomposition en séries et des méthodes de résolution d'équations différentielles. Introduction historique Au , Isaac Newton a développé de nouveaux outils de mathématiques pour résoudre des problèmes de physique (dont la question du mouvement des objets). Suivirent au James Clerk Maxwell, Lord Kelvin, William Rowan Hamilton. Au David Hilbert développa la théorie des espaces de Hilbert pour résoudre les équations intégrales, théorie qui se trouve au centre aujourd'hui de la mécanique quantique. La

Optimization methods and objective functions for analysis of metabolic network models

Zhaleh Hosseini

Computational studies of metabolism aim to systematically analyze the metabolic behaviour of biological systems in different conditions. Genome-scale metabolic network models (GEMs) capture the connection between elements of the network by applying stoichiometric balances while taking into account gene-protein-reaction associations. Several methods have already been developed for the analysis of these models. These methods are mainly used to optimize a single or combination of objective functions subject to different constraints. In this thesis, we have summarized the optimization methods and objective functions by classifying them based on biological and mathematical features. Particularly, we suggest reformulations to convert some of the complex optimization classes to simpler ones. One of the reformulations is the conversion of mixed-integer linear fractional programming (MILFP) to mixed-integer linear programming (MILP). We show that this conversion is useful in studying coupling relationships in thermodynamically constrained metabolic network models. Coupling determines how different components of the network such as metabolites or reactions are interrelated. Particularly, flux Coupling Analysis (FCA) is a method for evaluating the dependencies between metabolic reactions. In FCA, two reactions are considered as coupled if the activity of one, constrains the activity of the other. So far, FCA has been used for analyzing metabolic reactions in flux-balanced models. In this work, we developed a new formulation, Thermodynamic Flux Coupling Analysis (TFCA), which calculates flux couplings of metabolic models that are subjected to thermodynamic constraints. With TFCA, we show that adding thermodynamic constraints can significantly change the coupling relationship of reactions of the network. Moreover, we show that calculating coupling relations helps in reducing the number of combinations of bidirectional reactions (BDRs), which in turn will facilitate the analysis of the metabolic network. In addition to proposing several mathematical reformulations to gain global optimality, we also addressed the issue of finding the proper cellular objective function in different conditions of cellular metabolism. This is not always straight-forward, since the metabolic activities of some organisms are not well-characterized, e.g., metabolism of dormancy phase in some bacteria and parasites. In this thesis, we studied the metabolic behaviour of dormant malaria parasite using genome-scale model of Plasmodium falciparum. We examined known and novel objective functions and scored them based on the modelâs consistency with experimental gene expression data. Our results suggested that minimizing energy dissipation can best describe the metabolic activities of the malaria parasites in the dormancy phase. In the last chapter, we focus on studying another poorly characterized metabolic system that is the process of iron reduction in Clostridium acetobutylicum. Research has shown that this organism can reduce Fe(III), but the mechanism behind this reduction is yet to be identified. In this thesis, we analyzed the metabolism of C. acetobutylicum using its reconstructed genome-scale metabolic network model and experimental transcriptomics data in the presence or absence of Fe(III). By performing several computational studies, we suggested that NAD(P) is involved in the reduction of iron and is the potential physiological electron donor to Fe(III).

EPFL2020

Who Started This Rumor? Quantifying the Natural Differential Privacy of Gossip Protocols

Rachid Guerraoui, Hadrien Hendrikx

Gossip protocols (also called rumor spreading or epidemic protocols) are widely used to disseminate information in massive peer-to-peer networks. These protocols are often claimed to guarantee privacy because of the uncertainty they introduce on the node that started the dissemination. But is that claim really true? Can the source of a gossip safely hide in the crowd? This paper examines, for the first time, gossip protocols through a rigorous mathematical framework based on differential privacy to determine the extent to which the source of a gossip can be traceable. Considering the case of a complete graph in which a subset of the nodes are curious, we study a family of gossip protocols parameterized by a "muting" parameter s: nodes stop emitting after each communication with a fixed probability 1-s. We first prove that the standard push protocol, corresponding to the case s = 1, does not satisfy differential privacy for large graphs. In contrast, the protocol with s = 0 (nodes forward only once) achieves optimal privacy guarantees but at the cost of a drastic increase in the spreading time compared to standard push, revealing an interesting tension between privacy and spreading time. Yet, surprisingly, we show that some choices of the muting parameter s lead to protocols that achieve an optimal order of magnitude in both privacy and speed. Privacy guarantees are obtained by showing that only a small fraction of the possible observations by curious nodes have different probabilities when two different nodes start the gossip, since the source node rapidly stops emitting when s is small. The speed is established by analyzing the mean dynamics of the protocol, and leveraging concentration inequalities to bound the deviations from this mean behavior. We also confirm empirically that, with appropriate choices of s, we indeed obtain protocols that are very robust against concrete source location attacks (such as maximum a posteriori estimates) while spreading the information almost as fast as the standard (and non-private) push protocol. LIPIcs, Vol. 179, 34th International Symposium on Distributed Computing (DISC 2020), pages 8:1-8:18

Schloss Dagstuhl, Leibniz-Zentrum2020

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most sophisticated tasks involving decision making, can be reduced to solving certain optimization problems. These advances however, bring several new challenges to the field of algorithm design. The first of them is related to the ever-growing size of instances, these optimization problems need to be solved for. In practice, this forces the algorithms for these problems to run in time linear or nearly linear in their input size. The second challenge is related to the emergence of new, harder and harder problems which need to be dealt with. These problems are in most cases considered computationally intractable because of complexity barriers such as NP completeness, or because of non-convexity. Therefore, efficiently computable relaxations for these problems are typically desired. The material of this thesis is divided into two parts. In the first part we attempt to address the first challenge. The recent tremendous progress in developing fast algorithm for such fundamental problems as maximum flow or linear programming, demonstrate the power of continuous techniques and tools such as electrical flows, fast Laplacian solvers and interior point methods. In this thesis we study new algorithms of this type based on continuous dynamical systems inspired by the study of a slime mold Physarum polycephalum. We perform a rigorous mathematical analysis of these dynamical systems and extract from them new, fast algorithms for problems such as minimum cost flow, linear programming and basis pursuit. In the second part of the thesis we develop new tools to approach the second challenge. Towards this, we study a very general form of discrete optimization problems and its extension to sampling and counting, capturing a host of important problems such as counting matchings in graphs, computing permanents of matrices or sampling from constrained determinantal point processes. We present a very general framework, based on polynomials, for dealing with these problems computationally. It is based, roughly, on encoding the problem structure in a multivariate polynomial and then recovering the solution by means of certain continuous relaxations. This leads to several questions on how to reason about such relaxations and how to compute them. We resolve them by relating certain analytic properties of the arising polynomials, such as the location of their roots or convexity, to the combinatorial structure of the underlying problem. We believe that the ideas and mathematical techniques developed in this thesis are only a beginning and they will inspire more work on the use of dynamical systems and polynomials in the design of fast algorithms.

EPFL2018