20 citations · 33 across the 29 of their papers we have counts for
41 papers
Open Problems in Mathematical Logic
George Barmpalias, Su Gao, Jialiang He +8
These open problems were presented in the Problem Sessions held during the Tianyuan Workshop on Definability and Computation, June 22-26, 2026. The problems are organized into sect…
Speedability of computably approximable reals and their approximations
George Barmpalias, Nan Fang, Wolfgang Merkle +1
An approximation of a real is a sequence of rational numbers that converges to the real. An approximation is left-c.e. if it is computable and nondecreasing and is d.c.e. if it is…
Open Problems in Computability Theory and Descriptive Set Theory
George Barmpalias, Nikolay Bazhenov, Chi Tat Chong +11
These open problems were presented in the Problem Sessions held during the Tianyuan Workshop on Computability Theory and Descriptive Set Theory, June 16-20, 2025. The problems are…
Collision-resistant hash-shuffles on the reals
George Barmpalias, Xiaoyan Zhang
Oneway real functions are effective maps on positive-measure sets of reals that preserve randomness and have no effective probabilistic inversions. We construct a oneway real funct…
Complexity of inversion of functions on the reals
George Barmpalias, Mingyang Wang, Xiaoyan Zhang
We study the complexity of deterministic and probabilistic inversions of partial computable functions on the reals.
Computable one-way functions on the reals
George Barmpalias, Xiaoyan Zhang
A major open problem in computational complexity is the existence of a one-way function, namely a function from strings to strings which is computationally easy to compute but hard…
Dimensionality and randomness
George Barmpalias, Xiaoyan Zhang
Arranging the bits of a random string or real into k columns of a two-dimensional array or higher dimensional structure is typically accompanied with loss in the Kolmogorov complex…
Compression of enumerations and gain
George Barmpalias, Xiaoyan Zhang, Bohua Zhan
We study the compressibility of enumerations in the context of Kolmogorov complexity, focusing on strong and weak forms of compression and their gain: the amount of auxiliary infor…
Growth and irreducibility in path-incompressible trees
George Barmpalias, Xiaoyan Zhang
We study effective randomness-preserving transformations of path-incompressible trees. Some path-incompressible trees with infinitely many paths do not compute perfect path-random…
Randomness below complete theories of arithmetic
George Barmpalias, Wei Wang
We show that degrees containing a complete extensions of arithmetic have the random join property: they are the supremum of any random real they compute, with another random real.…
Aspects of Muchnik's paradox in restricted betting
George Barmpalias, Lu Liu
Muchnik's paradox says that enumerable betting strategies are not always reducible to enumerable strategies whose bets are restricted to either even rounds or odd rounds. In other…
Irreducibility of enumerable betting strategies
George Barmpalias, Lu Liu
We study the problem of whether a betting-strategy can be decomposed into an equivalent set of simpler betting-strategies, such as betting-strategies that bet on a restricted set o…
Gács-Kučera's Theorem Revisited by Levin
George Barmpalias, Alexander Shen
Leonid Levin (arxiv.org/abs/cs/0503039v14, p.7) published a new (and very nice) proof of Gács-Kučera's theorem that occupies only a few lines when presented in his style. We try to…
Pathwise-random trees and models of second-order arithmetic
George Barmpalias, Wei Wang
A tree is pathwise-random if all of its paths are Martin-Lof random. We show that (a) no weakly 2-random real computes a perfect pathwise-random tree; it follows that the class of…
Granularity of wagers in games and the possibility of savings
George Barmpalias, Nan Fang
In a casino where arbitrarily small bets are admissible, any betting strategy M can be modified into a savings strategy that, not only is successful on each casino sequence where M…
Monotonous betting strategies in warped casinos
George Barmpalias, Nan Fang, Andrew Lewis-Pye
Suppose that the outcomes of a roulette table are not entirely random, in the sense that there exists a successful betting strategy. Is there a successful `separable' strategy, in…
The idemetric property: when most distances are (almost) the same
George Barmpalias, Neng Huang, Andrew Lewis-Pye +4
We introduce the \emph{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 among…
Equivalences between learning of data and probability distributions, and their applications
George Barmpalias, Nan Fang, Frank Stephan
Algorithmic learning theory traditionally studies the learnability of effective infinite binary sequences (reals), while recent work by [Vitanyi and Chater, 2017] and [Bienvenu et…
Algorithmic learning of probability distributions from random data in the limit
George Barmpalias, Frank Stephan
We study the problem of identifying a probability distribution for some given randomly sampled data in the limit, in the context of algorithmic learning theory as proposed recently…
Compression of data streams down to their information content
George Barmpalias, Andrew Lewis-Pye
According to Kolmogorov complexity, every finite binary string is compressible to a shortest code -- its information content -- from which it is effectively recoverable. We investi…
Aspects of Chaitin's Omega
George Barmpalias
The halting probability of a Turing machine,also known as Chaitin's Omega, is an algorithmically random number with many interesting properties. Since Chaitin's seminal work, many…
Limits of the Kucera-Gacs coding method
George Barmpalias, Andrew Lewis-Pye
Every real is computable from a Martin-Loef random real. This well known result in algorithmic randomness was proved by Kucera and Gacs. In this survey article we discuss various a…
The probability of a computable output from a random oracle
George Barmpalias, Douglas Cenzer, Christopher P. Porter
Consider a universal Turing machine that produces a partial or total function (or a binary stream), based on the answers to the binary queries that it makes during the computation.…
On the existence of a strong minimal pair
George Barmpalias, Mingzhong Cai, Steffen Lempp +1
We show that there is a strong minimal pair in the computably enumerable Turing degrees.