Biography

My supervisor is George Barmpalias.

Interests
  • mathematical logic
  • recursion theory
  • Kolmogorov complexity
  • algorithmic randomness
Education

  • BSc in Mathematics, 2022

    Xi'an Jiaotong University

Articles

George Barmpalias, Xiaoyan Zhang (2024). Computable one-way functions on the reals.

PDF arxiv link

George Barmpalias, Xiaoyan Zhang (2024). Dimensionality and randomness.

PDF arxiv link

George Barmpalias, Xiaoyan Zhang (2024). Growth and irreducibility in path-incompressible trees.

PDF DOI published version arxiv link

George Barmpalias, Xiaoyan Zhang, Bohua Zhan (2023). Compression of enumerations and gain.

PDF arxiv link

Talks

Computable one-way functions on the reals
Abstract One-way functions are the functions that are easy to compute but hard to invert. In terms of oracle Turing machines, we can formalize the notion of computable functions from reals to reals, and define it to be one-way if computable functions almost everywhere fails to invert it.
Jul 15, 2024 12:00 AM Singapore
Slides
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
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

Open problems

Randomness of Index Sets
Let $U$ be a universal prefix-free Turing machine. Given $X\subset\omega$, let $\Omega[X]=\sum_{U(\sigma)\downarrow\in X}2^{-|\sigma|}$. The following are straight forward observations: $\{\Omega[X]:X\subset\omega\}=[0,\Omega]$. For each $n$ there is a $\Delta^0_{n+1}$ set $X$ such that $A[X]$ is $n$-random.
Jul 17, 2024 1 min read
$n$-r.e. plus left-r.e.
Definitions Let $A\subset\omega$. $A$ is $n$-r.e. if there is a computable function $f(a,s)$ such that for all $a\in\omega$, $f(a,0)=0$, $|\{s:f(a,s)\neq f(a,s+1)\}|\leq n$, $\lim_{s\to\infty}f(a,s)=\chi_A(a)$. Note that $1$-r.e. sets are just r.e. sets; $2$-r.
Nov 1, 2023 2 min read
Disk Game
The game Given parameters $(l,c,q)$. For convenience you can assume that $l$ is very large, $c=4$ and $q=1/2$. Consider the following game between a coder and a destroyer. The coder has spaces $f(\tau)$ indexed by $\tau\in 2^{\leq l}$ (all binary strings of length $\leq l$ which are called codes).
Nov 1, 2023 1 min read
String Cover
Definitions Let $K(\cdot)$ denote the Komogorov complexity. $2^{<\omega}$ is the set of all binary strings of finite length. $\log$ is the logarithm with base $2$. For $\sigma\in 2^{<\omega}$, an $(n,c)$-cover of $\sigma$ is a finite set of strings $A_\sigma$ such that
Nov 1, 2023 1 min read
Even Number Game
The game Given $k$, consider the following game of $2$ players. In each round, player 1 chooses a set $R$ of $k$ natural numbers that he has not yet chosen earlier player 2 chooses an even number $n\in[\min R,\max R]$, that he has not yet chosen earlier If player 2 is unable to make a move at some round, he loses the game; otherwise he wins.
Apr 6, 2023 1 min read
See all posts

Contact

  • zhangxy@ios.ac.cn
  • Zhongguancun South 4th Street No.4, Haidian District, Beijing 100190
  • Desk 112, 3rd floor, building 5 of Software Park