Articles by year

Speedability of computably approximable reals and their approximations
G. Barmpalias, N. Fang, W. Merkle, I. Titov
Inf. Comput. (2026) | pdf

Collision-resistant hash-shuffles on the reals
G. Barmpalias and X. Zhang
Inf. Comput. 309 (2026) | pdf

Compression of enumerations and gain
G. Barmpalias, X. Zhang, B. Zhan
Submitted (2026) | pdf

Dimensionality and randomness
G. Barmpalias and X. Zhang
ACM Trans. Comput. Logic (2026) | pdf

Complexity of inversion of functions on the reals
G. Barmpalias, M. Wang and X. Zhang
Math. Struct. Comput. Sci. 35 (2025) | pdf

Computable one-way functions on the reals
G. Barmpalias and X. Zhang
Inf. Comput. 306 (2025) | pdf | slides

Pathwise-random trees and models of second-order arithmetic
G. Barmpalias and W. Wang
Inf. Comput. 299 (2024) | Link | pdf | Poster

Growth and irreducibility in path-incompressible trees
G. Barmpalias and X. Zhang
Inf. Comput. 297 (2024) | Link | pdf | Poster

Gacs-Kucera's Theorem Revisited by Levin
G. Barmpalias and A. Shen
Theor. Comput. Sci. 947 (2023) | pdf

Randomness below complete theories of arithmetic
G. Barmpalias and W. Wang
Inf. Comput. 290 (2023) | Link | pdf | Poster

Granularity of wagers in games and the possibility of savings
G. Barmpalias and N. Fang
Inf. Comput. 275 (2020) | pdf

Monotonous betting strategies in warped casinos
G. Barmpalias, N. Fang and A. Lewis-Pye
Inf. Comput. 271 (2020) | pdf | Poster

Compression of data streams down to their information content
G. Barmpalias and A. Lewis-Pye
IEEE Trans. Inf. Theory 65(7) (2019) | pdf | GitHub | Poster

The idemetric property: when most distances are (almost) the same
G. Barmpalias, N. Huang, A. Lewis-Pye, A. Li, X. Li, Y. Pan, T. Roughgarden
Proc. R. Soc. A 475(2222) (2019) | Online | pdf | GitHub

Minority population in the one-dimensional Schelling model of segregation
G. Barmpalias, R. Elwes and A. Lewis-Pye
J. Stat. Phys. 173(5) (2018) | Download | pdf | Citations | GitHub | Poster

Optimal redundancy in computations from random oracles
G. Barmpalias and A. Lewis-Pye
J. Comput. Syst. Sci. 92 (2018) | pdf | Citations

Equivalences between learning of data and probability distributions, and their applications
G. Barmpalias, N. Fang and F. Stephan
Inf. Comput. 262 (2018) | pdf

Digital morphogenesis via Schelling segregation
G. Barmpalias, R. Elwes and A. Lewis-Pye
Nonlinearity 31 (2018) | pdf | Citations | GitHub | Poster (10MB)

Pointed computations and Martin-Loef randomness
G. Barmpalias, A. Lewis-Pye and A. Li
Computability 7(2-3) (2018) | pdf

Aspects of Chaitin's Omega
G. Barmpalias
Algorithmic Randomness: Progress and Prospects. Springer 2018 | pdf

Limits of the Kucera-Gacs coding method
G. Barmpalias and A. Lewis-Pye
South Eastern Logic Symp. in Logic. World Scientific 2018 | pdf

The probability of a computable output from a random oracle
G. Barmpalias, D. Cenzer and C. P. Porter
ACM Trans. Comput. Logic 18(3) (2017) | pdf

Differences of halting probabilities
G. Barmpalias and A. Lewis-Pye
J. Comput. Syst. Sci. 89 (2017) | pdf | Citations

Kobayashi compressibility
G. Barmpalias and R. G. Downey
Theor. Comput. Sci. 675 (2017) | pdf

Random numbers as probabilities of machine behaviour
G. Barmpalias, D. Cenzer and C. P. Porter
Theor. Comput. Sci. 673 (2017) | pdf | Slides

Computing halting probabilities from other halting probabilities
G. Barmpalias and A. Lewis-Pye
Theor. Comput. Sci. 660 (2017) | pdf

A note on the differences of computably enumerable reals
G. Barmpalias and A. Lewis-Pye
Proc. Int. Symp. Computability and Complexity (in honour of Rod Downey's 60th birthday), LNCS 10010, Springer, 2017 | pdf

Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
G. Barmpalias, N. Fang and A. Lewis-Pye
J. Comput. Syst. Sci. 82 (2016) | pdf

Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
G. Barmpalias, A. Lewis-Pye and J. Teutsch
Inf. Comput. 251 (2016) | pdf

Unperturbed Schelling Segregation in Two and Three Dimensions
G. Barmpalias, R. Elwes and A. Lewis-Pye
J. Stat. Phys. 164(6) (2016) | pdf | Citations | GitHub

On the existence of a strong minimal pair
G. Barmpalias, M. Cai, S. Lempp and T. Slaman
J. Math. Logic 15(1) (2015) | pdf

Integer-valued betting strategies and Turing degrees
G. Barmpalias, R. Downey and M. McInerney
J. Comput. Syst. Sci. 81 (2015) | pdf | Citations

Tipping Points in 1-Dimensional Schelling Models with Switching Agents
G. Barmpalias, R. Elwes and A. Lewis-Pye
J. Stat. Phys. 158 (2015) | pdf | Citations | GitHub

Exact pairs for the ideal of the $K$-trivial sequences in the Turing degrees
G. Barmpalias and R. Downey
J. Symb. Logic 79(3) (2014) | pdf | Citations

The typical Turing degree
G. Barmpalias, A. R. Day and A. E. M. Lewis
Proc. Lond. Math. Soc. 109(1) (2014) | pdf

Digital morphogenesis via Schelling segregation
G. Barmpalias, R. Elwes and A. Lewis-Pye
FOCS 2014, 55th Annual IEEE Symp. on Foundations of Computer Science, Oct. 18-21, Philadelphia. Watch our presentation in FOCS 2014. Also see Elwes' blog post | pdf

The information content of typical reals
G. Barmpalias and A. Lewis-Pye
In Turing's Ideas - Their Significance and Impact. Birkhauser/Springer 2014 | pdf

Universal computably enumerable sets and initial segment prefix-free complexity
G. Barmpalias
Inf. Comput. 233 (2013) | pdf

Algorithmic randomness and measures of complexity
G. Barmpalias
Bull. Symbolic Logic 19(3) (2013) | pdf

Kolmogorov complexity and computably enumerable sets
G. Barmpalias and A. Li
Ann. Pure Appl. Logic 164 (2013) | pdf

On the gap between trivial and nontrivial initial segment prefix-free complexity
G. Barmpalias and M. Baartse
Theory Comput. Syst. 52 (2013) | pdf | Citations

Analogues of Chaitin's Omega in the computably enumerable sets
G. Barmpalias, R. Holzl, A. E.M. Lewis, and W. Merkle
Inf. Process. Lett. 113(5-6) (2013) | pdf | Citations

Universality probability of a prefix-free machine
G. Barmpalias and D. L. Dowe
Philos. Trans. R. Soc. A 370 (2012) | pdf | Citations

Measure and cupping in the Turing degrees
G. Barmpalias and A. E.M. Lewis
Proc. Am. Math. Soc. 140(10) (2012) | pdf | Citations

Randomness notions and partial relativization
G. Barmpalias, J. Miller, and A. Nies
Israel J. Math. 191(2) (2012) | pdf | Citations

Tracing and domination in the Turing degrees
G. Barmpalias
Ann. Pure Appl. Logic 163 (2012) | pdf

Compactness arguments with effectively closed sets for the study of relative randomness
G. Barmpalias
J. Logic Comput. 22(4) (2012) | pdf

Lower bounds in the Turing degrees revisited
G. Barmpalias and A. Nies
J. Logic Comput. 22(4) (2012) | pdf

Resolute sets and initial segment complexity
G. Barmpalias and R.G. Downey
Proc. 12th Asian Logic Conf. 2012, World Scientific | pdf

K-trivials are never continuously random
G. Barmpalias, N. Greenberg, A. Montalban and T. Slaman
Proc. 11th Asian Logic Conf. World Scientific 2012 | pdf

On the number of infinite sequences with trivial initial segment complexity
G. Barmpalias and T. Sterkenburg
Theor. Comput. Sci. 412 (2011) | pdf

Chaitin's halting probability and the compression of strings using oracles
G. Barmpalias and A. E.M. Lewis
Proc. R. Soc. A 467 (2011) | pdf

Kolmogorov complexity of initial segments of sequences and arithmetical definability
G. Barmpalias and C. Vlek
Theor. Comput. Sci. 412 (2011) | pdf | Citations

Strings with trivial Kolmogorov Complexity
G. Barmpalias
Int. J. Softw. Informatics 5(4) (2011) | pdf

Upper bounds on ideals in the Turing degrees
G. Barmpalias and A. Nies
Ann. Pure Appl. Logic 162 (2011) | pdf

Jump inversions inside effectively closed sets and applications to randomness
G. Barmpalias, R. Downey, and K. M. Ng
J. Symb. Log. 76(2) (2011) | pdf | Citations

Elementary differences between the degrees of unsolvability and degrees of compressibility
G. Barmpalias
Ann. Pure Appl. Logic 161 (2010) | pdf | Citations

Relative randomness and cardinality
G. Barmpalias
Notre Dame J. Formal Logic 51(2) (2010) | pdf | Citations

The Importance of $\Pi^0_1$ Classes in Effective Randomness
G. Barmpalias, A. E.M. Lewis, and K.-M. Ng
J. Symb. Logic 75(1) (2010) | pdf | Citations

Working with strong reducibilities above totally $\omega$-c.e. and array computable degrees
G. Barmpalias, R. Downey, and N. Greenberg
Trans. Am. Math. Soc. 362 (2010) | pdf | Citations

K-trivial degrees and the jump-traceability hierarchy
G. Barmpalias, R. Downey, and N. Greenberg
Proc. Am. Math. Soc. 137 (2009) | pdf | Citations

Non-Cupping, Measure and Computably Enumerable Splittings
G. Barmpalias and A. Morphett
Math. Struct. Comput. Sci. 19 (2009) | pdf

$K$-triviality of closed sets and continuous functions
G. Barmpalias, D. Cenzer, J. Remmel, and R. Weber
J. Logic Comput. 19 (2009) | pdf

$\Pi^0_1$ classes, LR degrees and Turing degrees
G. Barmpalias, A. E.M. Lewis, and F. Stephan
Ann. Pure Appl. Logic 156(1) (2008) | pdf

Randomness, Lowness and Degrees
G. Barmpalias, A. E.M. Lewis, and M. Soskova
J. Symb. Logic 73(2) (2008) | pdf | Citations

Algorithmic Randomness of Continuous Functions
G. Barmpalias, P. Brodhead, D. Cenzer, J.B. Remmel, and R. Weber
Arch. Math. Logic 46(7-8) (2008) | pdf | Citations

Algorithmic Randomness of Closed Sets
G. Barmpalias, P. Brodhead, D. Cenzer, S. Dashti, and R. Weber
J. Logic Comput. 17 (2007) | pdf | Citations

Post's Programme for the Ershov Hierarchy
G. Barmpalias, B. Afshari, S. B. Cooper, and F. Stephan
J. Logic Comput. 17 (2007) | pdf | Citations

Randomness and the Linear degrees of computability
G. Barmpalias and A. E.M. Lewis
Ann. Pure Appl. Logic 145(3) (2007) | pdf | Citations

A cappable almost everywhere dominating computably enumerable degree
G. Barmpalias and A. Montalban
Electr. Notes Theor. Comput. Sci. 167 (2007). Proc. of the 3rd Int. Conf. Computability and Complexity in Analysis (CCA 2006) | pdf

$K$-trivial closed sets and continuous functions
G. Barmpalias, D. Cenzer, J. Remmel, and R. Weber
3rd Computability in Europe Conf. Siena 2007. Springer Lect. Notes Comput. Sci. 4497 (2007) | pdf

Working with the LR Degrees
G. Barmpalias, A.E.M. Lewis, M. Soskova
Proc. 4th Int. Conf. Theory and Applications of Models of Computation, Shanghai, May 2007. Springer Lect. Notes Comput. Sci., LNCS 4484, 2007 | pdf

Random Non-Cupping Revisited
G. Barmpalias
J. Complexity 22 (2006) | pdf

The Hypersimple-free c.e. wtt degrees are dense in the c.e. wtt degrees
G. Barmpalias and A. E.M. Lewis
Notre Dame J. Formal Logic 47(3) (2006) | pdf

A c.e. real that cannot be sw-computed by any $\Omega$ number
G. Barmpalias and A. E.M. Lewis
Notre Dame J. Formal Logic 47(2) (2006) | pdf | Citations

Random Reals and Lipschitz Continuity
G. Barmpalias and A. E.M. Lewis
Math. Struct. Comput. Sci. 16(5) (2006) | pdf | Citations

The $ibT$ Degrees of C.E. Sets are Not Dense
G. Barmpalias and A. E.M. Lewis
Ann. Pure Appl. Logic 141 (2006) | pdf Citations

Immunity properties and the n-c.e. hierarchy
G. Barmpalias, B. Afshari, and S.B. Cooper
Proc. 3rd Ann. Conf. Theory and Applications of Models of Computation, TAMC06, Beijing 2006. Springer Lect. Notes Comput. Sci. 3959 (2006) | pdf

Hypersimplicity and Semicomputability in the Weak Truth Table Degrees
G. Barmpalias
Arch. Math. Logic 44 (2005) | pdf Citations

$h$-Monotonically Computable Real Numbers
G. Barmpalias, X. Zheng, and R. Rettinger
Math. Logic Quart. 51 (2005) | pdf

Computably enumerable sets in the Solovay and the Strong Weak Truth Table Degrees
LNCS Vol. 3526, Proc. of the CiE conf. 2005 in Amsterdam | pdf

Approximation Representations for Reals and Their WTT Degrees
G. Barmpalias
Math. Logic Quart. 50 (2004) | pdf

Approximation Representations for $\Delta_2$ Reals
G. Barmpalias
Arch. Math. Logic 43 (2004) | pdf

The Approximation Structure of a Computably Approximable Real
G. Barmpalias
J. Symb. Logic 68 (2003) | pdf

A Transfinite Hierarchy of Reals
G. Barmpalias
Math. Logic Quart. 49 (2003) | pdf

On the Monotonic Computability of Semi-computable Real Numbers
G. Barmpalias and X. Zheng
Lect. Notes Comput. Sci. 2731 (2003) Springer-Verlag | pdf

On 0'-computable reals
G. Barmpalias
Electr. Notes Theor. Comput. Sci. Vol. 66(1) Elsevier 2002