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
  Last updated: Monday, 19 June 2023 Copyright © 2024 Barmpalias