# Publications in Journals

 Granularity of wagers in games and the possibility of savings George Barmpalias and Nan Fang Information and Computation 275 (2020). Summary  PDF  BibTex Monotonous betting strategies in warped casinos George Barmpalias, Nan Fang and Andy Lewis-Pye Information and Computation 271 (2020). Summary  PDF  BibTex Compression of data streams down to their information content George Barmpalias and Andy Lewis-Pye IEEE Transactions on Information Theory 65(7) (2019). Summary  PDF  BibTex  GitHub  Poster (11MB) The idemetric property: when most distances are (almost) the same George Barmpalias, Neng Huang, Andrew Lewis-Pye, Angsheng Li, Xuechen Li, Yicheng Pan, Tim Roughgarden Proceedings of the Royal Society A 475(2222) (2019). Online. Summary  PDF  BibTex  GitHub Minority population in the one-dimensional Schelling model of segregation George Barmpalias, Richard Elwes and Andy Lewis-Pye Journal of Statistical Physics 173(5), 2018, 1408--1458. Download. Summary  PDF  BibTex  GitHub  Poster (10MB) Optimal redundancy in computations from random oracles George Barmpalias and Andrew Lewis-Pye Journal of Computer and System Sciences 92 (2018) 1--8. Summary  PDF  BibTex Equivalences between learning of data and probability distributions, and their applications George Barmpalias, Nan Fang and Frank Stephan Information and Computation 262 (2018) 123--140. Summary  PDF  BibTex Digital morphogenesis via Schelling segregation George Barmpalias, Richard Elwes and Andy Lewis-Pye Nonlinearity 31 (2018) 1593-1638 Summary  PDF  BibTex  GitHub  Poster (10MB) Pointed computations and Martin-Loef randomness George Barmpalias and Andrew Lewis-Pye and Angsheng Li Computability vol. 7, no. 2-3, pp. 171-177, 2018. Summary  PDF   BibTex The probability of a computable output from a random oracle George Barmpalias, Douglas Cenzer and Christopher P. Porter ACM Transactions on Computational Logic Volume 18 Issue 3 (2017). Summary  PDF   BibTex Differences of halting probabilities George Barmpalias and Andy Lewis-Pye Journal of Computer and System Sciences 89 (2017) 349--360. Summary  PDF  BibTex Kobayashi compressibility George Barmpalias and Rodney G. Downey Theoretical Computer Science 675 (2017) 89-100. Summary  PDF  BibTex Random numbers as probabilities of machine behaviour George Barmpalias, Douglas Cenzer and Christopher P. Porter Theoretical Computer Science 673 (2017) 1-18. Summary  PDF  BibTex Computing halting probabilities from other halting probabilities George Barmpalias and Andy Lewis-Pye Theoretical Computer Science 660 (2017) 16-22. Summary  PDF  BibTex Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega George Barmpalias, Nan Fang and Andy Lewis-Pye Journal of Computer and System Sciences 82 (2016) 1283-1299. Summary  PDF  BibTex Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers George Barmpalias, Andy Lewis-Pye and Jason Teutsch Information and Computation 251 (2016) 287-300. Summary  PDF  BibTex Unperturbed Schelling Segregation in Two and Three Dimensions George Barmpalias, Richard Elwes and Andy Lewis-Pye Journal of Statistical Physics 164(6) (2016) 1460-1487. Summary  PDF  BibTex  GitHub On the existence of a strong minimal pair George Barmpalias, Mingzhong Cai, Steffen Lempp and Theodore Slaman Journal of Mathematical Logic Vol.15, No.1 (2015) 1550003 (28 pages) Summary  PDF  BibTex Integer-valued betting strategies and Turing degrees George Barmpalias, Rod Downey and Michael McInerney Journal of Computer and System Sciences 81 (2015) 1387-1412. Summary  PDF  BibTex Tipping Points in 1-Dimensional Schelling Models with Switching Agents George Barmpalias, Richard Elwes and Andy Lewis-Pye Journal of Statistical Physics (2015) 158:806-852 Summary  PDF  BibTex GitHub Exact pairs for the ideal of the $K$-trivial sequences in the Turing degrees George Barmpalias and Rod Downey Journal of Symbolic Logic Volume 79, Issue 03, September 2014, pp 676 - 692 Summary  PDF  BibTex The typical Turing degree George Barmpalias, A. R. Day and Andrew E.M. Lewis Proc. Lond. Math. Soc. (2014) 109 (1). pp. 1-39. Summary  PDF  BibTex Universal computably enumerable sets and initial segment prefix-free complexity George Barmpalias Information and Computation. 233 (2013) 41-59 Summary  PDF  BibTex Algorithmic randomness and measures of complexity George Barmpalias Bulletin of Symbolic logic (2013) 19(3):318-350 Summary  PDF  BibTex Kolmogorov complexity and computably enumerable sets George Barmpalias and Angsheng Li Annals of Pure and Applied Logic (2013) 164:1187-1200 Summary  PDF  BibTex On the gap between trivial and nontrivial initial segment prefix-free complexity George Barmpalias and Martijn Baartse Theory of Computing Systems. (2013) 52:28-47 Summary  PDF  BibTex Analogues of Chaitin's Omega in the computably enumerable sets George Barmpalias, Rupert Holzl, Andrew E.M. Lewis and Wolfgang Merkle Information Processing Letters (2013) 113(5-6):171-178. Summary  PDF  BibTex Universality probability of a prefix-free machine George Barmpalias and David L. Dowe Philosophical Transactions of the Royal Society A 2012 370, 3488-3511 Summary  PDF  BibTex Measure and Cupping in the Turing Degrees George Barmpalias and Andrew E.M. Lewis Proceedings of the American Mathematical Society Volume 140, Number 10 (2012) 3607-3622. Summary  PDF  BibTex Randomness Notions and Partial Relativization George Barmpalias, Joe Miller and Andre Nies Israel Journal of Mathematics, Volume 191, Number 2 (2012), 791-816 Summary  PDF  BibTex Tracing and domination in the Turing degrees George Barmpalias Annals of Pure and Applied Logic 163 (2012): 500-505 Summary  PDF  BibTex Compactness arguments with effectively closed sets for the study of relative randomness George Barmpalias Journal of Logic and Computation (2012) 22(4): 679-691 Summary  PDF  BibTex Lower bounds in the Turing degrees revisited George Barmpalias and Andre Nies Journal of Logic and Computation (2012) 22(4): 693-699 Summary  PDF  BibTex On the number of infinite sequences with trivial initial segment complexity George Barmpalias and Tom Sterkenburg Theoretical Computer Science (2011) 412:7133-7146. Summary  PDF  BibTex Chaitin's halting probability and the compression of strings using oracles George Barmpalias and Andrew E.M. Lewis Proc. R. Soc. A (2011) 467, 2912-2926. Summary  PDF  BibTex Kolmogorov complexity of initial segments of sequences and arithmetical definability George Barmpalias and Charlotte Vlek Theoretical Computer Science 412 (2011) 5656-5667 Summary  PDF  BibTex Strings with trivial Kolmogorov Complexity George Barmpalias International Journal of Software and Informatics, Volume 5, Issue 4 (2011), 609-623 Summary  PDF  BibTex Upper bounds on ideals in the Turing degrees George Barmpalias and Andre Nies Annals of Pure and Applied Logic 162 (2011) 465-473. Summary  PDF  BibTex Jump inversions inside effectively closed sets and applications to randomness George Barmpalias, Rod Downey and Keng-Meng Ng J. Symb. Log. 76(2): 491-518 (2011) Summary  PDF  BibTex Elementary differences between the degrees of unsolvability and degrees of compressibility George Barmpalias Annals of Pure and Applied Logic 161 (2010) 923-934 Summary  PDF  BibTex Relative randomness and cardinality George Barmpalias Notre Dame Journal of Formal Logic 51 Issue 2 (2010) 195-205 Summary  PDF  BibTex The Importance of $\Pi^0_1$ Classes in Effective Randomness George Barmpalias, Andrew E.M. Lewis and K.-M. Ng Journal of Symbolic Logic. Volume 75, Number 1 (2010) 387-400 Summary  PDF  BibTex Working with strong reducibilities above totally $\omega$-c.e. and array computable degrees George Barmpalias, Rod Downey and Noam Greenberg Transactions of the American Mathematical Society. 362 (2010), 777-813. Summary  PDF  BibTex K-trivial degrees and the jump-traceability hierarchy George Barmpalias, Rod Downey and Noam Greenberg Proceedings of the American Mathematical Society. 137 (2009) no. 6, 2099-2109 Summary  PDF  BibTex Non-Cupping, Measure and Computably Enumerable Splittings George Barmpalias and Anthony Morphett Mathematical Structures in Computer Science. vol. 19 (2009) 25-43 Summary  PDF  BibTex $K$-triviality of closed sets and continuous functions George Barmpalias, D. Cenzer, J. Remmel and R. Weber Journal of Logic and Computation 19 (2009), no. 1, 3-16 Summary  PDF  BibTex $\Pi^0_1$ classes, LR degrees and Turing degrees George Barmpalias, Andrew E.M. Lewis and Frank Stephan Annals of Pure and Applied Logic. Volume 156, Issue 1 (2008) pages 21-38 Summary  PDF  BibTex Randomness, Lowness and Degrees George Barmpalias, Andrew E.M. Lewis and Mariya Soskova Journal of Symbolic Logic. vol.73, Issue 2, pp. 559-577 (2008) Summary  PDF  BibTex Algorithmic Randomness of Continuous Functions George Barmpalias, P. Brodhead, D. Cenzer, J.B. Remmel and R. Weber Archive for Mathematical Logic, Volume 46, Numbers 7-8, pages 1041-1062, May 2008 Summary  PDF  BibTex Algorithmic Randomness of Closed Sets George Barmpalias, Paul Brodhead, Douglas Cenzer, Seyyed Dashti and Rebecca Weber Journal of Logic and Computation 2007 17:1041-1062. Summary  PDF  BibTex Post's Programme for the Ershov Hierarchy George Barmpalias, Bahareh Afshari, S.~Barry Cooper and Frank Stephan Journal of Logic and Computation 2007 17:1025-1040. Summary  PDF  BibTex Randomness and the Linear degrees of computability George Barmpalias and Andrew E.M. Lewis Annals of Pure and Applied Logic Volume 145, Issue 3, (2007), pages 252-257 Summary  PDF  BibTex Random Non-Cupping Revisited George Barmpalias Journal of Complexity 22 (2006) 850-857. Summary  PDF  BibTex The Hypersimple-free c.e. wtt degrees are dense in the c.e. wtt degrees George Barmpalias and Andrew E.M. Lewis Notre Dame Journal of Formal Logic Volume 47 Issue 3 (2006) 361-370 Summary  PDF  BibTex A c.e. real that cannot be sw-computed by any $\Omega$ number George Barmpalias and Andrew E.M. Lewis Notre Dame Journal of Formal Logic Volume 47 Issue 2 (2006) 197-209 Summary  PDF  BibTex Random Reals and Lipschitz Continuity George Barmpalias and Andrew E.M. Lewis Mathematical Structures in Computer Science Volume 16, issue 5 (2006) 737-749 Summary  PDF  BibTex The $ibT$ Degrees of C.E. Sets are Not Dense George Barmpalias and Andrew E.M. Lewis Annals of Pure and Applied Logic Volume 141, Issues 1-2 (2006) 51-60 Summary  PDF  BibTex Hypersimplicity and Semicomputability in the Weak Truth Table Degrees Archive for Math. Logic Vol.44, Number 8 (2005) 1045-1065 Summary  PDF  BibTex $h$-Monotonically Computable Real Numbers George Barmpalias, X. Zheng and R. Rettinger Mathematical Logic Quarterly, Vol.51 No.2 157-170 (2005) Summary  PDF  BibTex Approximation representations for reals and their wtt degrees George Barmpalias Mathematical Logic Quarterly, Vol. 50 number 4/5 (2004) 370-380 Summary  PDF  BibTex Approximation representations for $\Delta_2$ reals George Barmpalias Archive for Math. Logic, Volume 43, Number 8, (2004) p. 947-964 Summary  PDF  BibTex The approximation structure of a computably approximable real George Barmpalias J. Symbolic Logic, Vol.68, no.3 (2003) 885-922 Summary  PDF  BibTex A transfinite hierarchy of reals George Barmpalias Mathematical Logic Quarterly, Vol. 49, Number 2 (2003) 163-172. Summary  PDF  BibTex

# Publications in Conference Proceedings

 A note on the differences of computably enumerable reals George Barmpalias and Andy Lewis-Pye Proceedings of the International Symposium on Computability and Complexity (in honour of Rod Downey's 60th birthday), Lecture Notes in Computer Science 10010 Springer, 2017. Summary  PDF  BibTex Digital morphogenesis via Schelling segregation George Barmpalias, Richard Elwes and Andy Lewis-Pye FOCS 2014, 55th Annual IEEE Symposium on Foundations of Computer Science, Oct. 18-21, Philadelphia. Watch our presentation in FOCS 2014. Also see Elwes' blog post and our poster which won the Royal Society Picturing Sciencecompetition. Summary  PDF  BibTex Resolute sets and initial segment complexity George Barmpalias and R.G. Downey Proceedings of the 12th Asian Logic Conference 2012. World Scientific. Summary  PDF  BibTex K-trivials are never continuously random George Barmpalias, N. Greenberg, A. Montalban and T. Slaman Proceedings of the 11th Asian Logic Conference. Pages 51-58. World Scientific 2012. Summary  PDF  BibTex A cappable almost everywhere dominating computably enumerable degree George Barmpalias and Antonio Montalban Electronic Notes in Theoretical Computer Science Volume 167 (2007) 17-31. Proceedings of the Third International Conference on Computability and Complexity in Analysis (CCA 2006) Summary  PDF  BibTex Computably enumerable sets in the Solovay and the Strong Weak Truth Table Degrees LNCS Volume 3526, Proceedings of the CiE conference 2005 conference in Amsterdam (2005) 8-17 Summary  PDF  BibTex

# Book Chapters (Refereed)

 Aspects of Chaitin's Omega George Barmpalias Algorithmic Randomness: Progress and Prospects. Springer. Eds. J. Franklin and C. Porter (2018) Summary  PDF  BibTex Limits of the Kucera-Gacs coding method George Barmpalias and Andy Lewis-Pye SEALS (South Eastern Logic Symposium) Volume in Logic. Eds. D.Cenzer . World Scientific 2018. Summary  PDF  BibTex The information content of typical reals George Barmpalias and Andy Lewis-Pye In Turing's Ideas - Their Significance and Impact G. Sommaruga, T. Strahm (eds.),Basel, Birkhauser / Springer Basel, 2014. Summary  PDF  BibTex

# Extended abstracts in Conference Proceedings

 $K$-trivial closed sets and continuous functions George Barmpalias, D. Cenzer, J. Remmel and R. Weber CIE 2007, Computation and Logic in the Real World, Third Computability in Europe conference Siena, Italy, June 2007, S.B. Cooper, B. Loewe and A. Sorbi (Eds.) Springer Lecture Notes in Computer Science 4497 (2007), 135-145 Summary  PDF  BibTex Working with the LR Degrees George Barmpalias, Andrew E.M. Lewis, Mariya Soskova Theory and Applications of Models of Computation: 4th International Conference TAMC 2007, Shanghai, China, May 2007, Proceedings (J.-Y. Cai, S.B. Cooper, H. Zhu) Pages 89-99. Springer Lecture Notes in Computer Science, LNCS 4484, 2007 Summary  PDF  BibTex Immunity properties and the n-c.e. hierarchy George Barmpalias, Bahareh Afshari and S. Barry Cooper Proceedings of the Third Annual Conference on Theory and Applications of Models of Computation TAMC06, Beijing, May 2006 (Jin-Yi Cai, S. Barry Cooper, Angsheng Li) Springer Lecture Notes in Computer Science 3959 (2006) 694-703 . Summary  PDF  BibTex On the Monotonic Computability of Semi-computable Real Numbers George Barmpalias and Xizhong Zheng Lecture Notes in Computer Science 2731 (2003) 290-300, Springer-Verlag. Summary  PDF  BibTex On 0'-computable reals Electronic Notes in Theoretical Computer Science, Vol.66, Issue 1, pages 1-12.Eds. V. Brattka, M. Schroder and K. Weihrauch, Elsevier Science Publishers, 2002. Summary  BibTex

# Reviews

 Review of Lerman's "A framework for priority arguments" (Lecture Notes in Logic vol. 34. Cambridge University Press, NY, 2010, xvi + 176 pp.) Bulletin of Symbolic Logic, Volume 17 (2011), Issue 3, pp. 464-467. Summary  PDF  BibTex

# Recent Papers

 Pathwise-random trees and models of second-order arithmetic George Barmpalias and Wei Wang Submitted. Summary  PDF  BibTex

# PhD Thesis:

Computability and Applications to Analysis, U. of Leeds, Oct 2004
Summary  PDF  BibTex