Frank Stephan works in the areas of automata theory, recursion theory, inductive inference, computational complexity and algorithmic game theory.

In automata theory, Stephan mainly works about automatic structures. In joint work with researchers from Singapore and Auckland, he showed that there are no infinite automatic integral domains and he developped the concept of semiautomatic structures and inparticular groups of the same type. In inductive inference, Jain and Stephan studied with various coauthors the traditional recursion-theoretic model also introduced a new automata-theoretic model which is based on automatic famililies which are structures representing an infinite list of regular sets such that the membership relation is automatic in terms of indices and data-items.

In recursion theory, Stephan showed in his early work with Carl Jockusch that there is a cohesive set which is not high. Furthermore, he showed in some single-authored work that every set which is both, Martin-Loef random and PA-complete, is also Turing above the halting problem. Furthermore, Stephan solved a long-standing problem by showing that there are infinitely many bounded truth-table degrees within a truth-table degree; however, the same is not true for positive degrees. There are truth-table degrees which have 3 or 19 or 219 positive degrees. In his work, he listed out an infinite list of possible values on the number of positive degrees within a truth-table degree and showed that this number is always odd. Only in the case of the recursive truth-table degree, it can be 1, and it can also be infinite. It is open whether there are truth-table degrees with 5 or 7 or 9 or 11 or 13 or 15 or 17 positive degrees. Recent work investigated the structure of the numberings and showed that for every k-r.e. numbering of some sets there is a (k+1)-r.e. numbering of similar sets having the same Rogers semilattice; this new numbering is obtained by a general operator and this operator preserves not only the order of the sets but also for each specific numbering whether it is Friedberg, minimal, least, greatest or positive. Upcoming work with Ng, Yang and Yu deals with constructing recursive tree with uncountably many infinite branches such that all of them are recursive.

In computational complexity, early work with Beigel and Kummer showed that approximable sets cannot be NP-hard unless P = NP. This result was independently obtained by two other groups of authors and belongs to one of the best cited papers of Stephan.

In algorithmic game theory, Calude, Jain, Khoussainov, Li and Stephan found a quasipolynomial time algorithm for solving parity games and also showed that deciding parity games is fixed-parameter tractable with respect to the main parameter, the number of different values of the nodes in the parity game. This paper received the STOC 2017 best paper award. A follow-up publication with researchers from Liverpool showed that a modification of the quasipolynomial time algorithm furthermore uses only polynomial space.