Xiaoyan Zhang
Xiaoyan Zhang
Home
Articles
Talks
Open Problems
Contact
Light
Dark
Automatic
Kolmogorov Complexity
Dimensionality and randomness
Abstract The deficiency of a string is the maximum number of bits it can be compressed. We study sets of strings with finite (bounded) deficiency, which are called incompressible sets. Among them, observation shows that “thin” ones cannot be effectively transformed into “fat” ones unless they are complete.
Jul 11, 2024 12:00 AM
Singapore
Slides
Dimensionality and randomness
Abstract 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 complexity of the columns, which depends on k.
George Barmpalias
,
Xiaoyan Zhang
PDF
arxiv link
Growth and irreducibility in path-incompressible trees
Abstract We study effective randomness-preserving transformations of path-incompressible trees. Some path-incompressible trees with infinitely many paths do not compute perfect path-random trees with computable oracle-use. Sparse perfect path-incompressible trees can be effectively densified, almost surely.
George Barmpalias
,
Xiaoyan Zhang
PDF
DOI
published version
arxiv link
Compression of enumerations and gain
Abstract I will talk about how information in a recursive enumeration can be compressed, in the sense of relative Kolmogorov complexity (rK). We introduce a strong and a weak form of compression, and we also care about the gain of compressions.
Oct 17, 2023 12:00 AM
Hangzhou, China
Slides
Video
Compression of enumerations and gain
Abstract We study the compressibility of enumerations, and its role in the relative Kolmogorov complexity of computably enumerable sets, with respect to density. With repspect to a strong and a weak form of compression, we examine the gain: the amount of auxiliary information embedded in the compressed enumeration.
George Barmpalias
,
Xiaoyan Zhang
,
Bohua Zhan
PDF
arxiv link
Cite
×