651 64246

Frank Christian STEPHAN

Professor (NUS Department of Mathematics)
Joint Appointed with Department of Computer Science

  • Habilitation (Mathematics, University of Heidelberg, Germany, 1999)
  • Ph.D. (Dr. of Natural Sciences: Mathematics, University of Karlsruhe, Germany, 1990)
  • Diploma (Computer Science, University of Karlsruhe, Germany, 1989)

Frank Stephan is joint appointed by the Departments of Mathematics (primary) and Computer Science (secondary) of the National University of Singapore. He joint the NUS in 2004 after having worked at the National ICT Australia at the UNSW Sydney (2003-2004), the University of Heidelberg (1995-2003) and the University of Karlsruhe (T.H.) (1990-1995), where he studied Computer Science (Diploma) and Mathematics (Doctorate) from 1983 until 1990. Frank Stephan's research interests are within the areas of mathematical logic and theoretical computer science. In particular, he is working in recursion theory, inductive inference, automata theory, automatic structures, algorithmic randomness and computational complexity. Frank Stephan is an editor of the journal Computability and an associate editor of the Journal of Computer and System Sciences and a member of the editorial board of Information and Computation.



  • Automata Theory and in particular Automatic Structures

  • Learning Theory, mainly Inductive Inference

  • Recursion Theory

  • Infinite Games On Finite Graphs, mainly Parity Games

  • Algorithmic Randomness and Kolmogorov Complexity

  • Computational Complexity and Parameterised Complexity

  • Exponential Time Algorithms for NP-hard problems


Domination Properties, Ramsey-Type Theorems and Reverse Mathematics

This project explores proof-theoretical strength in tree generalizations of Ramsey's Theory, investigating links to induction strength and nonstandard models. It addresses recursion theory, growth behavior, and constructs co-r.e. trees, posing hypotheses to advance understanding in mathematical logic.




  • Carl Jockusch and Frank Stephan. A cohesive set which is not high. Mathematical Logic Quarterly 391:515-530, 1993 and 434:569-569, 1997.
  • Richard Beigel, Martin Kummer and Frank Stephan. Approximable Sets. Information and Computation 1202:304-314, 1995.
  • Efim Kinber and Frank Stephan. Language learning from texts: mindchanges, limited memory and monotonicity. Information and Computation 1232:224-241, 1995.
  • Martin Kummer and Frank Stephan. On the structure of degrees of inferability. Journal of Computer and System Sciences 522:214-238, 1996.
  • Frank Stephan. On the structures inside truth-table degrees. The Journal of Symbolic Logic 662:731-770, 2001.
  • André Nies, Frank Stephan and Sebastiaan A. Terwijn. Randomness, relativization and Turing degrees. The Journal of Symbolic Logic 702:515-535, 2005.
  • Bakhadyr Khoussainov, André Nies, Sasha Rubin and Frank Stephan. Automatic Structures: Richness and Limitations. Logical Methods in Computer Science 32, 2007.
  • Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan and Rolf Wiehagen. When unlearning helps. Information and Computation, 2065:694-709, 2008.
  • Bjørn Kjos-Hanssen, Wolfgang Merkle and Frank Stephan. Transactions of the American Mathematical Society 36310:5465-5480, 2011.
  • Sanjay Jain, Qinglong Luo and Frank Stephan. Learnability of automatic classes. Journal of Computer and System Sciences 786:1910-1927, 2012.
  • Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan. Deciding parity games in quasipolynomial time. Proceedings of the 49th Annual ACM SIGACT Sympositum on the Theory of Computing, STOC 2017, pages 252-263, 2017 Best Paper Award.
  • Sanjay Jain, Bakhadyr Khoussainov, Frank Stephan, Dan Teng and Siyuan Zou. Semiautomatic structures. Theory of Computing Systems 614:1254-1287, 2017.
  • Reductions between types of numberings.


  • STOC 2017 Best Paper Award for Quasipolynomial Time Algorithm solving Parity Games

  • EATCS-IPEC Nerode Prize 2021


Computational Complexity


In the News

29 September 2021
29 September 2021 - Professors Sanjay Jain and Frank Stephan and their research collaborators, lecturer Wei Li from the NUS ...


26 September 2018
It was a sweltering summer morning in July 2016, and the olive grove close to the town of Andria in ...