Research
I am a Professor in the Institute of Software, Chinese Academy of Sciences, working on mathematical logic, theoretical computer science and dynamical systems.
I have held positions in the University of Leeds, the University of Amsterdam and Victoria University of Wellington, before settling in Beijing with the 1000 young talents programme.
General
I work in Mathematics and Computer Science: Logic, Complexity and Information.
In pursuit of understanding complexity of information I have worked in:
Some problems from the literature that I have solved are listed here.
Press
Open problems
Projects
Completed projects in these areas include:
Oneway functions
Coding and compression
Dynamics in Networks
- The idemetric property. Proc. R. Soc. (2019) | [pdf]
- Minority population in the Schelling model. J. Stat. Phys. (2018) | [pdf]
- Morphogenesis via Schelling segregation. Nonlinearity (2018) | [pdf]
- Unperturbed Schelling Segregation. J. Stat. Phys. (2016) | [pdf]
- Tipping Points in Schelling Models. J. Stat. Phys. (2015) | [pdf]
Algorithmic information
- Chaitin's Omega in the enumerable sets. Inf. Process. Lett. (2013) | [pdf]
- Universal enumerable sets. Inf. Comput. (2013) | [pdf]
- Algorithmic measures of complexity. Bull. Symbolic Logic (2013) | [pdf]
- Kolmogorov complexity of enumerable sets. Ann. Pure Appl. Log. (2013) | [pdf]
- Randomness and relativization. Israel J. Math. (2012) | [pdf]
- Compression of strings using oracles. Proc. R. Soc. (2011) | [pdf]
Algorithmic Probability
- Aspects of Chaitin's Omega. In Algorithmic Randomness. Springer (2018) | [pdf]
- Probability of a computable output. ACM Trans. Comput. Logic (2017) | [pdf]
- Differences of halting probabilities. J. Comput. Syst. Sci. (2017) | [pdf]
- Random numbers as probabilities. Theor. Comput. Sci. (2017) | [pdf]
- Computing halting probabilities. Theor. Comput. Sci. (2017) | [pdf]
- Universality probability. Phil. Trans. R. Soc. (2012) | [pdf]
Degrees of Unsolvability
- Information of typical reals. In Turing's Ideas. Springer (2014) | [pdf]
- Typical Turing degrees. Proc. Lond. Math. Soc. (2014) | [pdf]
- Measure in the Turing degrees. Proc. Am. Math. Soc. (2012) | [pdf]
- Tracing and domination. Ann. Pure Appl. Log. (2012) | [pdf]
- Ideals in the Turing degrees. Ann. Pure Appl. Log. (2011) | [pdf]
Talks
Slides from selected talks on my research.
- Games, maps and randomness (Nankai 2025) [html] [pdf]
- Oneway functions on the reals (Kunming 2025) [pdf]
- Randomness below complete theories of arithmetic (Kochel, 2023) [pdf]
- Compression of enumerations and gain (Singapore, 2023) [pdf]
- Path-random trees and models of arithmetic (Astana, 2023) [pdf]
- Irreducibility and enumerability in betting strategies (Nanjing, 2021) [pdf]
- Equivalences in learning: data vs distributions (Singapore, 2021) [pdf]
- Savings and initial capital in betting games (Wuhan, 2019) [pdf]
- From randomness to segregation (Moskow, 2013) [pdf]
- Tracing and domination in the Turing degrees (Heidelberg, 2009) [pdf]
- Upper bounds for ideals in the Turing degrees (Singapore, 2009) [pdf]
People
Some researchers in Computability
- Eric Allender, Rutgers, The State University of New Jersey
- Klaus Ambos-Spies, University of Heidelberg, Germany
- Uri Andrews, University of Wisconsin–Madison
- Jeremy Avigad, Carnegie Mellon University
- George Barmpalias, Chinese Academy of Sciences, Beijing
- Achilles Beros, University of Hawai‘i at Mānoa
- Laurent Bienvenu, Université de Bordeaux, France
- Vasco Brattka, Universität der Bundeswehr München, Germany
- Douglas Cenzer, University of Florida
- Peter Cholak, University of Notre Dame
- Chi Tat Chong, National University of Singapore
- Chris J. Conidis, College of Staten Island, CUNY
- Barbara Csima, University of Waterloo, Canada
- Adam Day, Victoria University of Wellington, New Zealand
- David Diamondstone, Google
- Rod Downey, Victoria University of Wellington, New Zealand
- Damir D. Dzhafarov, University of Connecticut
- Rachel Epstein, Georgia College
- Santiago Figueira, Universidad de Buenos Aires, Argentina
- Ekaterina Fokina, Vienna University of Technology, Austria
- Lance Fortnow, Georgia Institute of Technology
- Johanna N.Y. Franklin, Hofstra University
- Harvey Friedman, The Ohio State University
- Hristo A. Ganchev, Sofia University, Bulgaria
- Peter Gerdes, Oakland University
- Sergei S. Goncharov, Novosibirsk State University, Russia
- Noam Greenberg, Victoria University of Wellington, New Zealand
- Serge Grigorieff, Université Paris VII Denis Diderot
- Péter Gács, Boston University
- Valentina Harizanov, George Washington University
- Matthew Harrison-Trainor, Victoria University of Wellington, New Zealand
- Peter Hertling, Universität der Bundeswehr München, Germany
- Denis Hirschfeldt, University of Chicago
- Jeff Hirst, Appalachian State University
- John Hitchcock, University of Wyoming
- Meng-Che "Turbo" Ho, Purdue University
- Mathieu Hoyrup, Université de Lorraine, France
- Rupert Hölzl, Universität der Bundeswehr München, Germany
- Emmanuel Jeandel, University of Lorraine, Paris
- Carl Jockusch, University of Illinois at Urbana-Champaign
- Asher Kach, Code.org
- Iskander Sh. Kalimullin, Kazan Federal University, Russia
- Bart Kastermans, KPN, the Netherlands
- Mushfeq Khan, University of Hawai‘i at Mānoa
- Bakhadyr Khoussainov, University of Auckland, New Zealand
- Takayuki Kihara, Nagoya University, Japan
- Bjørn Kjos-Hanssen, University of Hawai‘i at Mānoa
- Julia F. Knight, University of Notre Dame
- Ulrich Kohlenbach, Technische Universität Darmstadt, Germany
- Kenneth Kunen, University of Wisconsin–Madison
- Rutger Kuyper, Metaswitch
- Steffen Lempp, University of Wisconsin–Madison
- Manuel Lerman, University of Connecticut
- Leonid Levin, Boston University
- Andy Lewis-Pye, London School of Economics
- Jack Lutz, Iowa State University
- Alberto Marcone, Università di Udine, Italy
- Andrew Marks, UCLA
- Luca San Mauro, Vienna University of Technology, Austria
- Elvira Mayordomo, Universidad de Zaragoza, Spain
- Timothy H. McNicholl, Iowa State University
- Alexander G. Melnikov, Massey University, New Zealand
- Wolfgang Merkle, University of Heidelberg, Germany
- Joseph R. Mileti, Grinnell College
- Joseph S. Miller, University of Wisconsin–Madison
- Russell G. Miller, Queens College and the Graduate Center, CUNY
- Arnie Miller, University of Wisconsin–Madison
- Kenshi Miyabe, Meiji University, Japan
- Benoit Monin, Université Paris-Est Créteil, France
- Antonio Montalbán, University of California, Berkeley
- Andrey Morozov, Novosibirsk State University, Russia
- Lawrence S. Moss, Indiana University
- Carl Mummert, Marshall University
- Satyadev Nandakumar, Indian Institute of Technology, Kanpur
- Anil Nerode, Cornell University
- Keng Meng Ng, Nanyang Technological University, Singapore
- André Nies, University of Auckland, New Zealand
- Ludovic Patey, Institut Camille Jordan, Lyon, France
- Arno Pauly, Swansea University, Wales
- Christopher Porter, Drake University
- Jan Reimann, Pennsylvania State University
- Jennifer Chubb Reimann, University of San Francisco
- Cristóbal Rojas, Universidad Andrés Bello, Santiago, Chile
- Stéphane Le Roux, Université libre de Bruxelles, Belgium
- Jason Rute, Pennsylvania State University
- Noah Schweber, University of Wisconsin–Madison
- Alexander Shen, Université de Montpellier, France
- Richard Shore, Cornell University
- Stephen G. Simpson, Pennsylvania State and Vanderbilt Universities
- Theodore A. Slaman, University of California, Berkeley
- Robert I. Soare, University of Chicago
- Reed Solomon, University of Connecticut
- Andrea Sorbi, Università degli Studi di Siena, Italy
- Ivan N. Soskov, Sofia University, Bulgaria
- Alexandra A. Soskova, Sofia University, Bulgaria
- Mariya I. Soskova, University of Wisconsin–Madison
- Frank Stephan, National University of Singapore
- Sebastiaan A. Terwijn, Radboud University Nijmegen, The Netherlands
- Henry Towsner, University of Pennsylvania
- Daniel Turetsky, Victoria University of Wellington, New Zealand
- Nikolai K. Vereshchagin, Moscow State University, Russia
- Rebecca Weber, ReveDreams.com
- Klaus Weihrauch, FernUniversität Hagen, Germany
- Linda Brown Westrick, Pennsylvania State University
- Guohua Wu, Nanyang Technological University, Singapore
- Keita Yokoyama, Japan Advanced Institute of Science and Technology
- Liang Yu, Nanjing University, China
- Yang Yue, National University of Singapore