George Barmpalias
Professor, State Key Lab of Computer Science
Institute of Software, Chinese Academy of Sciences
2004 Ph.D. in Mathematics. Faculty of Science, University of Leeds, U.K.
2000 Mathematics Degree. University of Thessaloniki, Greece
2018- Professor at the Chinese Academy of Sciences (Beijing, Institute of Software)
2016-2017 Senior Lecturer at the Victoria University of Wellington (New Zealand)
2015-2018 Associate Professor at the Chinese Academy of Sciences (Beijing, Institute of Software)
2011-2014 Research Fellow and Lecturer at Victoria University of Wellington (New Zealand)
2011-2014 Research Fellow at the Chinese Academy of Sciences (Beijing, Institute of Software)
2009-2011 Lecturer in Mathematics at the ILLC of the University of Amsterdam
2007-2009 Research Fellow and Lecturer in Mathematics, Victoria University of Wellington
2004-2007 Research Fellow in Mathematics, University of Leeds, United Kindom
2003-2004 Registration Marshal and IT demonstrator, University of Leeds, United Kindom
2000-2003 Mathematics Tutor, University of Leeds, United Kindom
2022 Distinguished Research Professor (CAS)
2020 Joint (with Wang Wei) National Natural Science grant on "Reverse mathematics"
2019 National Natural Science Foundation grant on "Non-Uniform coding"
2018 Research fund for international young scientists from the National Natural Science Foundation
2017 National Natural Science Foundation grant for the 1000 young talents program
2016 Institute of Software grant for the 1000 young talents program
2015 One thousand young talents scholar (Central Organization Dept., Chinese Comm. Party)
2014 Research fund for international young scientists from the National Natural Science Foundation
2013 Royal Society prize for Picturing science poster in the Infographics category
2013 Research fund for international young scientists from the National Natural Science Foundation
2012 International Young Scientist Award from the Chinese Academy of Sciences
2011 1-year Research Fellowship for International Young scientists by the Chinese Academy
2004 3-year EPSRC Research Fellowship
2001 3-year grant for studying abroad by the University of Thessaloniki, Greece
2001 3-year partial EPSRC doctoral grant from the University of Leeds
2001 Essay Prize by the Advanced Reasoning Forum and Wadsworth Publishing Company
2020 PC co-chair for PLS 2021 (13th Panhellenic Logic Symposium, Volos, Greece)
2019 Program committee member for CCR 2019 (Astana, Kazakhstan)
2018 Program committee member for PLS 2019 (12th Panhellenic Logic Symposium, Crete, Greece)
2017 Program committee member for FAW (International Frontiers of Algorithmics)
2017 Organizer of the Networks Seminar, Institute of Software, Chinese Academy of Sciences
2016 Member of University Wellbeing Staff Committee at Victoria University of Wellington
2015 Program committee for CiE 2016 (Computability in Europe), Paris, France.
2015 Program committee for CCR 2015 (Computability, Complexity and Randomness), Heidelberg
2014 Managing Editor of TCS volume with proceedings from of TAMC 2012
2012 Program committee for the TAMC conference in Beijing
2012 Organizing committee for the Turing year in China and TAMC conference in Beijing
2009 Organizer of the Logic seminar, University of Amsterdam (until 2011)
2007 Organizing committee for the CiE (Computability in Europe) conference in Siena
2007 External examiner for the PhD exam of Maria Libera Affatato, University of Siena
2002 Chair of the Staff/Postgraduate Committee, School of Mathematics, University of Leeds
2022 Cheng Shichao: Coding games and descriptive complexity MSc in CAS
2019 Fang Nan: Restricted Coding and Betting PhD in Heidelberg (formal supervisor Wolfgang Merkle)
2010 Charlotte Vlek: Definability in the degrees of Randomness. MSc. Univ. Amsterdam
2010 Tom Sterkenburg On the number of K-trivial sequences. MSc. Univ. Amsterdam
2009 Anthony Morphett Degrees of Computability and Randomness. PhD. (with Cooper), Univ. Leeds
Theory of Computation (Graduate) Beijing, Fall 2022
Network Science (Graduate) Beijing, Summer 2019
Individual Strategy and Social Structure (Graduate) Beijing, Spring 2012
Network Science (Honors) Wellington, Fall 2016
Optimization (Undergraduate) Wellington, Fall 2016
Optimization (Undergraduate) Wellington, Fall 2016
Linear Algebra II (Undergraduate) Wellington, Fall 2014, Fall 2016
Theory of Computation (U) Wellington, Spring 2014
Algebra and Discrete Mathematics (Undergraduate) Wellington Fall 2008
Theory of Computation (Graduate) Wellington Spring 2007, Spring 2008
Mathematical Logic (Undergraduate) Amsterdam Fall 2010
Introduction to Logic in Computer Science (Graduate) Amsterdam Fall 2010
Axiomatic Set Theory (Undergraduate) Amsterdam Spring 2010
Project on Randomness and Computability (Graduate) Amsterdam Winter and Summer 2010
Model Theory (national master class) Amsterdam Spring 2010
Special topics in mathematical logic (Graduate) Amsterdam Spring 2010
Complexity Theory (Graduate) Amsterdam Fall 2009
Descriptive Set Theory (Graduate) Amsterdam Fall 2009
Algorithmic Randomness (Graduate) Leeds Spring 2006
Randomness and Effective measure (Graduate) Leeds Fall 2006
Discrete Mathematics and Linear Algebra (Tutorials) Leeds Spring 2004
Real analysis (Tutorials) Leeds Fall 2002, Fall 2003
Group Theory (Tutorials) Leeds Fall 2001, Spring 2002
Calculus (Tutorials) Leeds Spring 2001, Fall 2002
2019 Chinese Annual Conference on Mathematical Logic Chongqing. Special.
2019 Computability Theory and Foundations of Mathematics, Wuhan. Plenary.
2019 Logic Workshop, Nanjing. Special.
2018 Computability Theory and Foundations of Mathematics, Tokyo. Plenary.
2018 Chinese Logic Conference, Guizhou. Special session.
2018 South East Logic Symposium (SEALS), Florida. Plenary.
2018 Mathematisches Forschungsinstitut Oberwolfach, Germany. Plenary.
2017 Dagstuhl Seminar 17081: Computability Theory, Dagstuhl. Special session.
2016 Banff Int. Research Station for Math. Innovation and Discovery, Oaxaca. Plenary
2016 South East Logic Symposium (SEALS), Florida. Keynote.
2016 Mathematics Colloquium,University of Florida, USA.
2015 The Second Delta Logic Workshop,Fudan, Shanghai
2015 10th Int. Conf. on Computability, Complexity and Randomness, Heidelberg. Plenary.
2014 IMS meeting in NUS (Singapore) on Algorithmic Randomness. Plenary.
2014 Shonan meeting ``Algorithmic Randomness and ComplexityÓ, Japan. Plenary.
2013 Eighth conference Computability, Complexity and Randomness, Moscow. Plenary.
2012 7th Int. Conf. on Computability, Complexity and Randomness, Cambridge, U.K. Plenary.
2012 Asian Logic Conference 2012, Sun-Yat Sen, September
2012 Oberwolfach meeting: Computability, February
2012 Dagstuhl Seminar: Computability, Complexity and Randomness, July
2012 Modern Developments in Computability Theory and Applications, Guangzhou, Sun-Yat Sen
2012 Mathematical Legacy of Turing (Public opening of SAS, Spitalfields Day) Cambridge
2011 Logic Colloquium, European ASL meeting in Barcelona. Plenary
2011 8th Panhellenic Logic Symposium, Ioannina
2010 5th Conference on Computability, Complexity and Randomness, Notre Dame. Plenary
2009 European Association of Symbolic Logic meeting, Sofia
2009 Computability in Europe (CiE) meeting in Heidelberg
2009 4th International Conference on Computability, Complexity and Randomness, Marseille
2008 Third conference Computability, Complexity and Randomness, Nanjing
2007 1st joint meeting of the New Zealand and American mathematical societies
2007 American ASL meeting in Gainesville Florida
2007 4th Conference on Theory and Applications of Models of Computation TAMC07 Shanghai
2006 American annual meeting of the Association for symbolic logic, Montreal
2005 2nd Conference on Theory and Applications of Models of Computation TAMC05 Kunming
Granularity of wagers in games and the possibility of savings
George Barmpalias and Nan Fang
Information and Computation 275 (2020)
Monotonous betting strategies in warped casinos
George Barmpalias, Nan Fang and Andy Lewis-Pye
Information and Computation 271 (2020)
Compression of data streams down to their information content
George Barmpalias and Andy Lewis-Pye
IEEE Transactions on Information Theory 65(7) (2019)
The idemetric property: when most distances are (almost) the same
George Barmpalias, Neng Huang, Andrew Lewis-Pye, Angsheng Li, Xuechen Li, Yicheng Pan, Tim Roughgarden
Proceedings of the Royal Society A vol 475, Issue 2222, 2019.
Minority population in the one-dimensional Schelling model of segregation
George Barmpalias, Richard Elwes and Andy Lewis-Pye
Journal of Statistical Physics In press.
Optimal redundancy in computations from random oracles
George Barmpalias and Andrew Lewis-Pye
Journal of Computer and System Sciences 92 (2018) 1--8.
Equivalences between learning of data and probability distributions, and their applications
George Barmpalias, Nan Fang and Frank Stephan
Information and Computation 262 (2018) 123--140.
Aspects of Chaitin's Omega
George Barmpalias
Algorithmic Randomness: Progress and Prospects. Springer. Eds. J. Franklin and C. Porter (2018)
Limits of the Kucera-Gacs coding method
George Barmpalias and Andrew Lewis-Pye
SEALS (South Eastern Logic Symposium) Volume in Logic. Eds. D.Cenzer . World Scientific 2018.
Digital morphogenesis via Schelling segregation
George Barmpalias, Richard Elwes and Andy Lewis-Pye
Nonlinearity 31 (2018) 1593--1638
Pointed computations and Martin-Loef randomness
George Barmpalias and Andrew Lewis-Pye and Angsheng Li
Computability vol. 7, no. 2-3, pp. 171--177, 2018.
The probability of a computable output from a random oracle
George Barmpalias, Douglas Cenzer and Christopher P. Porter
ACM Transactions on Computational Logic Volume 18 Issue 3 (2017).
Differences of halting probabilities
George Barmpalias and Andy Lewis-Pye
Journal of Computer and System Sciences 89 (2017) 349--360.
Kobayashi compressibility
George Barmpalias and Rodney G. Downey
Theoretical Computer Science 675 (2017) 89--100.
Random numbers as probabilities of machine behaviour
George Barmpalias, Douglas Cenzer and Christopher P. Porter
Theoretical Computer Science 673 (2017) 1--18.
Computing halting probabilities from other halting probabilities
George Barmpalias and Andy Lewis-Pye
Theoretical Computer Science 660 (2017) 16--22.
Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
George Barmpalias, Nan Fang and Andy Lewis-Pye
Journal of Computer and System Sciences Volume 82 (2016) 1283-1299.
Tipping Points in 1-Dimensional Schelling Models with Switching Agents
George Barmpalias, Richard Elwes and Andy Lewis-Pye
Journal of Statistical Physics Volume 158 (2015) 806-852
Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
George Barmpalias, Andy Lewis-Pye and Jason Teutsch
Information and Computation (in press).
Unperturbed Schelling Segregation in Two and Three Dimensions
George Barmpalias, Richard Elwes and Andy Lewis-Pye
Journal of Statistical Physics 164(6) (2016) 1460-1487.
A note on the differences of computably enumerable reals
George Barmpalias and Andy Lewis-Pye
Festschrift volume for Downey's 60th birthday.Springer LNCS series, 2016.
Integer-valued betting strategies and Turing degrees
George Barmpalias, Rod Downey and Michael McInerney
Journal of Computer and System Sciences Volume 81 (2015) 1387-1412
On the existence of a strong minimal pair
George Barmpalias, Mingzhong Cai, Steffen Lempp and Theodore Slaman
Journal of Mathematical Logic Volume 15, No.1 (2015) 1550003 (28 pages)
Exact pairs for the ideal of the $K$-trivial sequences in the Turing degrees
George Barmpalias and Rod Downey
Journal of Symbolic Logic Volume 79, Issue 03, September 2014, pp 676-692.
Digital morphogenesis via Schelling segregation
George Barmpalias and Richard Elwes and Andy Lewis-Pye.
FOCS 2014, 55th Annual IEEE Symposium on Foundations of Computer Science, Oct. 18-21, Philadelphia.
The information content of typical reals
George Barmpalias and Andy Lewis-Pye.
In Turing's Ideas - Their Significance and Impact
G. Sommaruga, T. Strahm (eds.),Basel, Birkhauser/Springer Basel, 2014.
Universal computably enumerable sets and initial segment prefix-free complexity
George Barmpalias
Information and Computation 233 (2013) 41-59.
The typical Turing degree
George Barmpalias, Adam Day and Andy Lewis-Pye
Proceedings of the London Mathematical Society 109 (1) 2014. pp.1-39.
Kolmogorov complexity and computably enumerable sets
George Barmpalias and Angsheng Li
Annals of Pure and Applied Logic 164 (2013) pp. 1187-1200
Algorithmic randomness and measures of complexity
George Barmpalias
Bulletin of Symbolic logic 19 (2013)
Analogues of Chaitin's Omega in the computably enumerable sets
George Barmpalias and Rupert Holzl, Andrew E.M. Lewis and Wolfgang Merkle
Information Processing Letters (2013) 113(5-6):171-178.
On the gap between trivial and nontrivial initial segment prefix-free complexity,
George Barmpalias and Martijn Baartse
Theory of Computing Systems. 52:28-47 (2013).
Universality probability of a prefix-free machine
George Barmpalias and David L. Dowe
Philosophical Transactions of the Royal Society A 370:3488-3511 (2012).
Randomness Notions and Partial Relativization
George Barmpalias, Joe Miller and Andre Nies
Israel Journal of Mathematics 191(2) (2012) 791-816.
Low upper bounds in the Turing degrees revisited
George Barmpalias and Andre Nies
Journal of Logic and Computation 22(4):693-699 (2012) .
Resolute sequences in initial segment complexity
George Barmpalias and Rod Downey
Proceedings of the 12th Asian Logic Conference. World Scientific 2012.
Compactness arguments with effectively closed sets for the study of relative randomness,
George Barmpalias
Journal of Logic and Computation 22(4):679-691 (2012).
Tracing and domination in the Turing degrees
George Barmpalias
Annals of Pure and Applied Logic 163 (2012):500-505.
Measure and Cupping in the Turing Degrees
George Barmpalias and Andrew E.M. Lewis
Proceedings of the American Mathematical Society 140(10) (2012).
On the number of infinite sequences with trivial initial segment complexity,
George Barmpalias and Tom Sterkenburg
Theoretical Computer Science 412:7133-7146 (2011).
Kolmogorov complexity of initial segments of sequences and arithmetical definability,
George Barmpalias and Charlotte Vlek
Theoretical Computer Science 412:5656-5667 (2011).
Strings with trivial Kolmogorov Complexity
George Barmpalias
International Journal of Software and Informatics 5(4):609-623 (2011).
Chaitin's halting probability and the compression of strings using oracles,
George Barmpalias and Andrew E.M. Lewis
Proceedings of the Royal Society 467:2912-2926 (2011).
Upper bounds on ideals in the Turing degrees
George Barmpalias and Andre Nies
Annals of Pure and Applied Logic 162 (2011) 465-473.
Jump inversions inside effectively closed sets and applications to randomness
George Barmpalias, Rod Downey and Keng-Meng Ng
J. Symb. Log. 76(2):491-518 (2011)
K-trivials are never continuously random
George Barmpalias and Noam Greenberg and Antonio Montalban and Ted Slaman),
Proceedings of the 11th Asian Logic Conference. World Scientific (2011).
Working with strong reducibilities above totally omega-c.e. and array computable degrees
George Barmpalias and Rod Downey and Noam Greenberg
Transactions of the American Mathematical Society 362 (2010).
The importance of $\Pi^0_1$ classes in effective randomness
George Barmpalias and Andrew E.M. Lewis and K.-M. Ng
Journal of Symbolic Logic 75(1) (2010).
Relative randomness and cardinality
George Barmpalias
Notre Dame Journal of Formal Logic 51(2) (2010).
K-trivial degrees and the jump-traceability hierarchy
George Barmpalias and Rod Downey and Noam Greenberg
Proceedings of the American Mathematical Society 137(6) (2009).
K-triviality of closed sets and continuous functions
George Barmpalias and D. Cenzer, J. Remmel and R. Weber
Journal of Logic and Computation 19(1) (2009).
Non-Cupping, Measure and Computably Enumerable Splittings
George Barmpalias and Anthony Morphett
Mathematical Structures in Computer Science 19:25-43 (2009).
$\Pi^0_1$ classes, $LR$ degrees and Turing degrees
George Barmpalias and Andrew E.M. Lewis and Frank Stephan
Annals of Pure and Applied logic 156:21-38 (2008).
Randomness, Lowness and Degrees
George Barmpalias and Mariya Soskova and Andrew E.M. Lewis
Journal of Symbolic Logic 73(2):559-577 (2008).
Algorithmic Randomness of Continuous Functions
George Barmpalias and P. Brodhead, D. Cenzer, J.B. Remmel and R. Weber
Archive for Mathematical Logic 46(7-8):533-546 (2008).
Post's Programme for the Ershov Hierarchy
George Barmpalias and Bahareh Afshari, S. Barry Cooper and Frank Stephan
Journal of Logic and Computation 17:1025-1040 (2007)
Algorithmic Randomness of Closed Sets
George Barmpalias and Paul Brodhead, Douglas Cenzer, Seyyed Dashti and Rebecca Weber
Journal of Logic and Computation 17:1041-1062 (2007)..
Randomness and the Linear degrees of computability
George Barmpalias and Andrew E.M. Lewis
Annals of Pure and Applied Logic 145(3):252-257 (2007).
Working with the LR Degrees
George Barmpalias and Andrew E.M. Lewis, Mariya Soskova
Theory and Applications of Models
of Computation: 4th International Conference TAMC 2007, Shanghai, China
Proceedings
(J.-Y. Cai, S.B. Cooper, H. Zhu, eds. Springer LNCS 4484 (2007) 89-99.
K-trivial closed sets and continuous functions
George Barmpalias and D. Cenzer, J. Remmel and R. Weber
CIE 2007: Computation and Logic in the Real World
Third Conference on Computability in Europe, Siena, Italy
S.B. Cooper, B. Loewe and A. Sorbi (Eds.), Springer LNCS 4497 (2007), 135-145.
Random Non-Cupping Revisited
George Barmpalias
Journal of Complexity 22:850-857 (2006).
Immunity properties and the n-c.e. hierarchy
George Barmpalias and Bahareh Afshari and S. Barry Cooper
Theory and Applications of Models of Computation - Proceedings of the
Third Annual Conference on Computation and Logic, TAMC06, Beijing, May 2006 (Jin-Yi Cai, S. Barry Cooper, Angsheng Li, eds.),
Springer LNCS 3959:694-703 (2006).
A computably enumerable real which cannot be sw-computed by any Omega number
George Barmpalias and Andrew E.M. Lewis
Notre Dame Journal of Formal Logic 47(2)197-209 (2006).
The ibT Degrees of computably enumerable sets are Not Dense
George Barmpalias and Andrew E.M. Lewis
Annals of Pure and Applied Logic 141(1-2)51-60 (2006).
Random Reals and Lipschitz Continuity
George Barmpalias and Andrew E.M. Lewis
Mathematical Structures in Computer Science 16(5):737-749 (2006).
The Hypersimple-free c.e. wtt degrees are dense in the c.e. wtt degrees
George Barmpalias and Andrew E.M. Lewis
Notre Dame Journal of Formal Logic 47(3):361-370 (2006).
Hypersimplicity and Semicomputability in the Weak Truth Table Degrees
George Barmpalias
Archive for Mathematical Logic 44(8):1045-1065 (2005).
Computably enumerable sets in the Solovay and the Strong Weak Truth Table Degrees
George Barmpalias
Lecture Notes in Computer Science 3526:8-17 (2005).
h-Monotonically Computable Real Numbers
George Barmpalias and Xizhong Zheng and Robert Rettinger
Math. Log. Quart. 51(2):157-170 (2005).
Approximation representations for $\Delta^0_2$ reals
George Barmpalias
Archive for Math. Logic, 43(8):947-964 (2004).
Approximation representations for reals and their wtt degrees
George Barmpalias
Math. Log. Quart. 50(4/5):370-380 (2004).
The approximation structure of a computably approximable real
George Barmpalias
J. Symbolic Logic 68(3):885-922 (2003)
A transfinite hierarchy of reals
George Barmpalias
Mathematical Logic Quarterly 49(3):163-172 (2003).
On the monotonic computability of semi-computable real numbers
George Barmpalias and Xizhong Zheng
Lecture Notes in Computer Science 2731:290-300 (2003)
On 0'-computable reals
George Barmpalias
Electronic Notes in Theoretical Computer Science, 66(1) (2002)
Eds. V. Brattka, M. Schroder and K. Weihrauch, Elsevier Science Publishers.