History of science | EPFL Graph Search

The history of science covers the development of science from ancient times to the present. It encompasses all three major branches of science: natural, social, and formal. Science's earliest roots can be traced to Ancient Egypt and Mesopotamia around 3000 to 1200 BCE. These civilizations' contributions to mathematics, astronomy, and medicine influenced later Greek natural philosophy of classical antiquity, wherein formal attempts were made to provide explanations of events in the physical world based on natural causes. After the fall of the Western Roman Empire, knowledge of Greek conceptions of the world deteriorated in Latin-speaking Western Europe during the early centuries (400 to 1000 CE) of the Middle Ages, but continued to thrive in the Greek-speaking Eastern Roman (or Byzantine) Empire. Aided by translations of Greek texts, the Hellenistic worldview was preserved and absorbed into the Arabic-speaking Muslim world during t

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

TimeRank: A dynamic approach to rate scholars using citations

Giovanni Colavizza, Massimo Franceschet

Rating has become a common practice of modern science. No rating system can be considered as final, but instead several approaches can be taken, which magnify different aspects of the fabric of science. We introduce an approach for rating scholars which uses citations in a dynamic fashion, allocating ratings by considering the relative position of two authors at the time of the citation among them. Our main goal is to introduce the notion of citation timing as a complement to the usual suspects of popularity and prestige. We aim to produce a rating able to account for a variety of interesting phenomena, such as positioning raising stars on a more even footing with established researchers. We apply our method on the bibliometrics community using data from the Web of Science from 2000 to 2016, showing how the dynamic method is more effective than alternatives in this respect.

Elsevier Science Bv2017

Tomographic imaging with harmonic holography in tissues of known refractive index distribution

Demetri Psaltis, Ye Pu

High-resolution imaging in thick biological tissues beyond a few transport mean free path of photons remains a formidable challenge to modern science and technology. Recent advancements in optical tomography have enabled the reconstruction of the three-dimensional (3D) refractive index distribution in biological samples, which is crucial in the prediction of light propagation in that sample. Here we propose a new technique for imaging second harmonic radiating imaging probes (SHRIMPs) through a tissue using harmonic holography based on the extracted refractive index map. We analyze the spatiotemporal intensity distribution of light pulses using a new model that separate scattering by orders (times of deflections) and show that wide-field excitation and detection of the SHG in tissues beyond one cm thickness is possible with resonant nonlinear plasmonic nanocavities as the SHRIMP. We demonstrate with numerical simulations that the 3D image of SHRIMPs can be extracted by matching the measured second harmonic speckle pattern with that predicted for each point in the sample given the refractive index. We analyze the impact of measurement error in the refractive index on the SNR of the recovered image. We further discuss the influence of the frequency-domain memory effect.

SPIE-INT SOC OPTICAL ENGINEERING2018

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

EPFL2018