3 papers
math.LO2025
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…
math.LO2016
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.
cs.CC2016
Pointed computations and Martin-Löf randomness
George Barmpalias, Andrew Lewis-Pye, Angsheng Li
Schnorr showed that a real is Martin-Loef random if and only if all of its initial segments are incompressible with respect to prefix-free complexity. Fortnow and independently Nie…