Recent Papers

Dimensionality and randomness
George Barmpalias and Xiaoyan Zhang
Submitted.
Summary PDF BibTex

Compression of enumerations and gain
George Barmpalias, Xiaoyan Zhang, and Bohua Zhan
Submitted.
Summary PDF BibTex Abstract (IMS 2023)

Aspects of Muchnik's paradox in restricted betting
George Barmpalias and Lu Liu
Submitted.
Summary PDF BibTex

Irreducibility of enumerable betting strategies
George Barmpalias and Lu Liu - Answers a question of Kastermans
Submitted.
Summary PDF BibTex

Publications in Journals

Pathwise-random trees and models of second-order arithmetic
George Barmpalias and Wei Wang - Answers a question of Chong et al.
Information and Computation 299 (2024) Link
Summary PDF BibTex

Growth and irreducibility in path-incompressible trees
George Barmpalias and Xiaoyan Zhang
Information and Computation 297 (2024) Link
Summary PDF BibTex

Gacs-Kucera's Theorem Revisited by Levin
George Barmpalias and Alexander Shen
Theoretical Computer Science 947 (2023)
Summary PDF BibTex

Randomness below complete theories of arithmetic
George Barmpalias and Wei Wang
Information and Computation 290 (2023) Link
Summary PDF BibTex Abstract (CCR 2023)

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
Answers a question of Brandt, Immorlica, Kamath and Kleinberg
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.
Answers a question of Becher, Figueira, Grigorieff, and Miller, and Nies
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
Answers a question of Nies
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
Answers a question in the book by Downey and Hirschfeldt
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
Answers a question of Wallace
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.
Answers a question of Jockusch
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
Answers a question of Simpson
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.
Answers a question in the book of Downey and Hirschfeldt
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.
Answers a question of Miller
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.
Answers a question of Calhoun
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

PhD Thesis:

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

George Barmpalias

Professor, State Key Lab of Computer Science

Institute of Software, Chinese Academy of Sciences