Welcome to my homepage. I'm an Associate Professor and Royal Society University Research Fellow in the mathematics department at the London School of Economics. My research interests concern algorithmic processes in their various forms. More specifically I work in computability, randomness, networks, complexity science, algorithmic game theory and learning.

In the links to the left you'll find pdfs of papers (earlier papers being published under my previous name Andrew Lewis).

Email: andy @ aemlewis.co.uk

Most recent projects


Sex vs Asex.

The question as to why most higher organisms reproduce sexually has remained open despite extensive research, and has been called ``the queen of problems in evolutionary biology''. Theories dating back to Weismann have suggested that the key must lie in the creation of increased variability in offspring, causing enhanced response to selection. Rigorously quantifying the effects of assorted mechanisms which might lead to such increased variability, and establishing that these beneficial effects outweigh the immediate costs of sexual reproduction has, however, proved problematic. In joint work with Antonio Montalban, we introduce an approach which does not focus on particular mechanisms influencing factors such as the fixation of beneficial mutants or the ability of populations to deal with deleterious mutations, but rather tracks the entire distribution of a population of genotypes as it moves across vast fitness landscapes. In this setting simulations now show sex robustly outperforming asex across a broad spectrum of finite or infinite population models. Concentrating on the additive infinite populations model, we are able to give a rigorous mathematical proof establishing that sexual reproduction acts as a more efficient optimiser of mean fitness, thereby solving the problem for this model. Some of the key features of this analysis carry through to the finite populations case.

A mathematical analysis of the evoltionary benefits of sexual reproduction, pdf.

Schelling segregation.

Schelling's model of segregation looks to explain the way in which particles or agents of two types may come to arrange themselves spatially into configurations consisting of large homogeneous clusters, i.e. connected regions consisting of only one type. As one of the earliest agent based models studied by economists and perhaps the most famous model of self-organising behaviour, it also has direct links to areas at the interface between computer science and statistical mechanics, such as the Ising model and the study of contagion and cascading phenomena in networks.

While the model has been extensively studied it has largely resisted rigorous analysis, prior results from the literature generally pertaining to variants of the model which are tweaked so as to be amenable to standard techniques from statistical mechanics or stochastic evolutionary game theory. Recently Brandt, Immorlica, Kamath and Kleinberg provided the first rigorous analysis of the unperturbed model, for a specific set of input parameters. In the following sequence of papers my co-authors George Barmpalias, Richard Elwes and I provide a rigorous analysis of the model's behaviour much more generally and establish some surprising forms of threshold behaviour, for the two and three dimensional as well as the one-dimensional model. The model is described precisely here.

Digital morphogenesis via Schelling segregation, to appear in FOCS 2014, pdf.

Tipping points in Schelling segregation, to appear in the Journal of Statistical Physics, pdf.

From randomness to order: Schelling segregation in two or three dimensions, pdf.

Minority population in the one-dimensional Schelling model of segregation, pdf.

Typicality and the Turing degrees.

The Turing degree of a real measures the computational difficulty of producing its binary expansion. Since Turing degrees are tailsets, it follows from Kolmogorov's 0-1 law that for any property which may or may not be satisfied by any given Turing degree, the satisfying class will either be of Lebesgue measure 0 or 1, so long as it is measurable. So either the typical degree satisfies the property, or else the typical degree satisfies its negation. Further, there is then some level of randomness sufficient to ensure typicality in this regard. In this paper, we prove results in a new programme of research which aims to establish the (order theoretically) definable properties of the typical Turing degree. Here also are the slides for the talk I gave on this stuff at the Colloquium Logicum 2012:

The typical Turing degree, Proceedings of the London Mathematical Society, Dec 2013, pdf.

Computable Structures

A computable structure is given by a computable domain, and then a set of computable relations and functions defined on that domain. The study of computable structures, going back as far as the work of Frohlich and Shepherdson, Rabin, and Malcev is part of a long-term programme to understand the algorithmic content of mathematics.

In mathematics generally, the notion of isomorphism is used to determine structures which are essentially the same. Within the context of effective (algorithmic) mathematics, however, one is presented with the possibility that pairs of computable structures may exist which, while isomorphic, fail to have a computable isomorphism between them. Thus the notion of computable categoricity has become of central importance: a computable structure S is computably categorical if any two computable presentations A and B of S are computably isomorphic. In this paper, my co-authors Downey, Kach, Lempp, Montalban, Turetsky and I, answer one of the longstanding questions in computable structure theory, showing the class of computably categorical structures has no simple structural or syntactic characterisation.

The complexity of computable categoricity, to appear in Advances in Mathematics, pdf.