4 papers
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…
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…
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…