Frank Christian STEPHAN
ProfessorProfessor (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.
RESEARCH AREAS
RESEARCH INTERESTS
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
RESEARCH PROJECTS
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.
RESEARCH GROUPS
TEACHING INNOVATIONS
SELECTED PUBLICATIONS
- 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.
AWARDS & HONOURS
STOC 2017 Best Paper Award for Quasipolynomial Time Algorithm solving Parity Games
EATCS-IPEC Nerode Prize 2021
MODULES TAUGHT
CS5230
Computational Complexity