The papers below are divided as cleanly as possible into subject areas. All authors are listed alphabetically. Most papers are under my previous name, Andrew Lewis.

The idemetric property: when most distances are (almost) the same.

We introduce the idemetric property, which formalises the idea that most nodes in a graph have similar distances between them, and which turns out to be quite standard amongst small-world network models. Modulo reasonable sparsity assumptions, we are then able to show that a strong form of idemetricity is actually equivalent to a very weak expander condition (PUMP). This provides a direct way of providing short proofs that small-world network models such as the Watts-Strogatz model are strongly idemetric (for a wide range of parameters), and also provides further evidence that being idemetric is a common property. We also consider how satisfaction of the idemetric property is relevant to algorithm design.

The idemetric property: when most distances are (almost) the same., with Barmpalias, Huang, Li, Li, Pan and Roughgarden, to appear in the Proceedings of the Royal Society A, pdf.

Sex vs Asex.

The question as to why most complex organisms reproduce sexually remains a very active research area in evolutionary biology. Theories dating back to Weismann have suggested that the key may lie in the creation of increased variability in offspring, causing enhanced response to selection. Under appropriate conditions, selection is known to result in the generation of negative linkage disequilibrium, with the effect of recombination then being to increase genetic variance by reducing these negative associations between alleles. It has therefore been a matter of significant interest to understand precisely those conditions resulting in negative linkage disequilibrium, and to recognise also the conditions in which the corresponding increase in genetic variation will be advantageous. In joint work with Antonio Montalban, we prove results establishing basic conditions under which negative linkage disequilibrium will be created, and describing the long term effect on population fitness. For infinite population models in which gene fitnesses combine additively with zero-epistasis, we show that, during the process of asexual propagation, a negative linkage disequilibrium will be created and maintained, meaning that an occurrence of recombination at any stage of the process will cause an immediate increase in fitness variance. In contexts where there is a large but finite bound on allele fitnesses, the non-linear nature of the effect of recombination on a population presents serious obstacles in establishing convergence to an equilibrium, or even the positions of fixed points in the corresponding dynamical system. We describe techniques for analysing the long term behaviour of sexual and asexual populations for such models, and use these techniques to establish conditions resulting in higher fitnesses for sexually reproducing populations.

Sex versus Asex: an analysis of the role of variance conversion, with Antonio Montalban, Theoretical Population Biology, 114, 2017, pdf.

Schelling segregation

Digital morphogenesis via Schelling segregation, with George Barmpalias and Richard Elwes.

One of the major contributions of the Nobel prize winning economist and game theorist Thomas Schelling was an elegant model of racial segregation, first described in 1969, which describes a very simple morphogenic process. Although the explicit concern is racial segregation, the analysis is sufficiently abstract that any situation in which objects of two types arrange themselves geographically according to a certain ‘intolerance’ – a preference not to be of a minority type in their neighbourhood – could constitute an interpretation. In 2012, Brandt, Immorlica, Kamath and Kleinberg provided the first rigorous analysis of the 1-dimensional unperturbed version of Schelling’s model, proving the behaviour of the model for a specific set of input parameters. Here we provide a rigorous analysis of the model’s behaviour much more generally, and establish that some surprising forms of threshold behaviour result. In fact, there are many situations in which an increased level of intolerance leads almost certainly to decreased segregation.

Digital morphogenesis via Schelling segregation, with Barmpalias and Elwes, FOCS 2014, 55th Annual IEEE Symposium on Foundations of Computer Science, Oct. 18-21, Philadelphia, pdf.

Tipping points in Schelling segregation, with Barmpalias and Elwes, Journal of Statistical Physics 158, 806-852, 2015, pdf.

From randomness to order: Schelling segregation in two or three dimensions, with Barmpalias and Elwes, Journal of Statistical Physics, 164 (6), 1460-1487, 2016, pdf.

Minority population in the one-dimensional Schelling model of segregation, with Barmpalias and Elwes,  Journal of Statistical Physics 173(5), 1408–1458, 2018, pdf.

Typicality in 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 these papers, we prove results in a new programme of research which aims to establish the (order theoretically) definable properties of the typical Turing degree, and the level of randomness required in order to guarantee typicality. One of the results establishes a quantitative solution to Spector’s question from the 50s, which asks for a characterisation of those degrees which have a strong minimal cover – measure 1 many degrees do.

The typical Turing degree, with George Barmpalias and Adam Day, Proceedings of the London Mathematical Society 109 (1), 1-39, 2014, pdf.

The information content of typical reals, with George Barmpalias, Turing’s ideas – their significance and impact, G. Sommaruga and T. Strahm (eds), Springer Basel 2014, pdf.

Measure and cupping in the Turing degrees, with George Barmpalias,
Proceedings of the American Mathematical Society, Volume 140, Number 10 (2012), 3607-3622, pdf.

Investigations in and around an old question of Yates

Yates’ question as to whether every minimal Turing degree has a strong minimal cover, remains one of the longstanding questions of degree theory. The papers below all resulted from my interest in Yates’ question and surrounding issues. The solution to the question of Slaman and Groszek – every non-computable perfect tree computes one of its non-computable paths – rules out all counterexamples I had previously conceived of. The solution to Sacks’ question from the 80s, as to whether there exist fixed point free minimal degrees, leaves the possibility that counterexamples to Yates’ question might be hyperimmune-free.

On a question of Slaman and Groszek,
Proceedings of the American Mathematical Society, 136, (2008), 3663-3668, pdf.

A fixed point free minimal degree, with Masahiro Kumabe,
Journal of the London Mathematical Society, (2009), 80 (3): 785-797, pdf.

A random degree with strong minimal cover,
Bulletin of the London Mathematical Society, (2007), 39 (5), 848-856, pdf.

\Pi^0_1 classes, strong minimal covers and hyperimmune-free degrees,
Bulletin of the London Mathematical Society, (2007), 39 (6): 892-910, pdf.

Strong minimal covers and a question of Yates: the story so far,
Proceedings of the Logic Colloquium (2006), pdf.

Cooperative behaviour on networks

Prisoner’s Dilemma games have become a well-established paradigm for studying the mechanisms by which cooperative behaviour may evolve in societies consisting of selfish individuals. Recent research has focussed on the effect of spatial and connectivity structure in promoting the emergence of cooperation in scenarios where individuals play games with their neighbors, using simple `memoryless’ rules to decide their choice of strategy in repeated games. While heterogeneity and structural features such as clustering have been seen to lead to reasonable levels of cooperation in very restricted settings, no conditions on network structure have been established which robustly ensure the emergence of cooperation in a manner which is not overly sensitive to parameters such as network size, average degree, or the initial proportion of cooperating individuals. Here we consider a natural random network model, with parameters which allow us to vary the level of `community’ structure in the network, as well as the number of high degree hub nodes. We investigate the effect of varying these structural features and show that, for appropriate choices of these parameters, cooperative behaviour does now emerge in a truly robust fashion and to a previously unprecedented degree. The implication is that cooperation (as modelled here by Prisoner’s Dilemma games) can become the social norm in societal structures divided into smaller communities, and in which hub nodes provide the majority of inter-community connections.

Establishing social cooperation: the role of hubs and community structure, with Cooper, Li, Pan and Yong, to appear in Network Science, pdf.

Compressing information using oracles

If a computer is given access to an oracle – the characteristic function of a set whose membership relation may or may not be algorithmically calculable – this may dramatically affect its ability to compress information and to determine structure in strings which might otherwise appear random. In the papers below we compare the compression power of different oracles. In particular, we establish the conjecture of Miller that there countably many oracles that compress information at most as well as the oracle A iff Chaitin’s halting probability \Omega is random relative to A.

Chaitin’s halting probability and the compression of strings using oracles, with George Barmpalias,
Proceedings of the Royal Society A, (2011), 467, 2912-2926, pdf.

\Pi^0_1 classes, LR degrees and Turing degrees, with George Barmpalias and Frank Stephan,
Annals of Pure and Applied Logic, 156 (2008) 21-38, Pdf.

Lowness, randomness and degrees, with George Barmpalias and Mariya Soskova,
Journal of Symbolic Logic, vol.73, Issue 2, pp. 559-577 (2008), Pdf.

Working with the LR Degrees, with George Barmpalias and Mariya Soskova,
Theory and Applications of Models of Computation: 4th International Conference TAMC 2007, Shanghai, China, May 2007, Springer Lecture Notes in Computer Science, LNCS 4484, (2007).

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 the paper below, we 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, with Downey, Kach, Lempp, Montalban and Turetsky, Advances in Mathematics 268, 423-466, 2015, pdf.

Basic structural properties of the Turing degrees

The Turing degree of a real measures the difficulty of producing its binary expansion, and is the central object of study in computability theory. In the papers below, we establish basic properties of this structure. Amongst other results, we resolve a question of Posner from the 80s concerning minimal complementation, a question of Odifreddi from the 80s concerning \Sigma02 minimal degrees, and a conjecture of Posner from the 70s concerning the generalised high degrees.

C.e. degrees and the meet property, with Durrant, Ng and Riley, Proceedings of the American Mathematical Society 144, 1735-1744, 2016, pdf.

The search for natural definability in the Turing degrees, to appear in a special issue of Computability,  pdf.

Extensions of embeddings below computably enumerable degrees, with Rod Downey, Antonio Montalban and Noam Greenberg, Transactions of the American Mathematical Society, 365, 2977-3018, 2013, pdf.

Properties of the jump classes,
Journal of Logic and Computation, (2012), 22 (4): 845-855, pdf.

A note on the join property,
Proceedings of the American Mathematical Society, 140 (2012), 707-714, pdf.

Joining up to the generalized high degrees, with Philip Ellison,
Proceedings of the American Mathematical Society, 138 (2010), 2949-2960, pdf.

The jump classes of minimal covers,
Logical Approaches to Computational Barriers, Second conference on Computability in Europe, CiE 2006, Lecture Notes in Computer Science, 307-318.

A single minimal complement for the c.e. degrees,
Transactions of the American Mathematical Society, 359 (2007), 5817-5865.

A partial solution to a question of Sacks,
New Computational Paradigms, proceedings of CiE 2005, Lecture Notes in Computer Science , 3526, 275-286.

On a question of Sacks: a partial solution on the positive side.

The minimal complementation property above 0′,
Mathematical Logic Quarterly, 51 (5), 470-492.

Properly \Sigma_2 minimal degrees and 0” complementation, with Barry Cooper and Yue Yang,
Mathematical Quarterly, 51, 274-276.

Finite cupping sets,
Archive for Mathematical Logic, 43, 845-858.

Minimal complements for degrees below 0′,
Journal of Symbolic Logic, 69 (4), 937-966.

The Medvedev and Muchnik lattices, and the enumeration degrees

The Medvedev and Muchnik lattices concern reducibilities between sets of reals – one set of reals is Muchnik reducible to a second, if given any element of the second set, one can compute some member of the first, i.e. the problem of producing an element of the first set is no harder than producing one of the second. If the reduction is uniform (the same Turing functional suffices in every case), then the first set is Medvedev reducible to the second.

Diagonally non-computable functions and bi-immunity, with Carl Jockusch,
Journal of Symbolic Logic 78 (3), 977-988, 2013, pdf.

Topological aspects of the Medvedev lattice, with Richard Shore and Andrea Sorbi,
Archive for Mathematical Logic, 50 (2011), 319-340, pdf.

Empty intervals in the e-degrees, with Andrea Sorbi and Thomas Kent,
Annals of Pure and Applied Logic, Volume 163, Issue 5 (2012), 567574, pdf.

The first-order theories of the Medvedev and Muchnik lattices, with Nies and Sorbi,
Proceedings of the 5th Conference on Computability in Europe: Mathematical Theory and Computational Practice, Lecture Notes in Computer Science, 5635, 324 – 331, pdf.

Algorithmic randomness (outside categories above), Pi01 classes and strong reducibilities

Compression of data streams down to their information content, with Barmpalias, to appear in IEEE Transactions on Information Theory, pdf.

Optimal asymptotic bounds on the oracle use in computations from Chaitin’s Omega, with Barmpalias and Fang, Journal of Computer and System Sciences, 82, 1283-1299, 2016, pdf.

Optimal redundancy in computations from random oracles, with Barmpalias, Journal of Computer and System Sciences (in press), pdf.

Differences of halting probabilities, with Barmpalias, Journal of Computer and System Sciences, 89, 349-360, 2017, pdf.

A note on the differences of computably enumerable reals, with Barmpalias, Proceedings of the International Symposium on Computability and Complexity, Lecture Notes in Computer Science, 10010, Springer, 2017, pdf.

Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers , with Barmpalias and Teutsch, Information and Computation, 251, 287-300, 2016, pdf.

Computing halting probabilities from other halting probabilities, with Barmpalias, Theoretical Computer Science, 660, 16-22, 2017, pdf.

Pointed computations and Martin-Loef randomness, with Barmpalias and Li, Computability (in press), pdf.

Limits of the Kucera-Gacs coding method, with Barmpalias, Post-proceedings volume of SEALS 2016, South Eastern Logic Symposium. World Scientific 2017, pdf.

Analogies of Chaitin’s \Omega in the c.e. sets, with George Barmpalias, Holzl and Merkle,
Information Processing Letters, (2013) 113(5-6):171-178, pdf.

The importance of \Pi^0_1 classes in effective randomness, with George Barmpalias and Keng-Meng Ng,
Journal of Symbolic Logic, Volume 75, Number 1 (2010), pdf.

On the degree spectrum of a \Pi^0_1 class, with Thomas Kent,
Transactions of the American Mathematical Society, 362 (2010), 5283-5319, pdf.

A weakly 2-random which is not GL_1, with Antonio Montalban and Andre Nies,
Lecture Notes in Computer Science, vol 4497.

The ibT degrees of c.e. sets are not dense, with George Barmpalias,
Annals of Pure and Applied Logic, volume 141, issues 1-2, (2006).

Randomness and the linear degrees of computability, with George Barmpalias,
Annals of Pure and Applied Logic, volume 145, issue 3 (2007), 252-257.

The hypersimple-free wtt degrees are dense in the c.e. wtt degrees, with George Barmpalias,
Notre Dame Journal of Formal Logic, volume 47 issue 3 (2006).

Random reals and Lipschitz continuity, with George Barmpalias,
Mathematical Structures in Computer Science, volume 16, issue 5 (2006).

A c.e. real that cannot be sw computed by any \Omega number, with George Barmpalias,
Notre Dame Journal of Formal Logic, vol 47 (2), 197-209.