Frank Stephan
Frank Stephan
National University of Singapore, Department of Mathematics and Department of Computer Science
Verified email at - Homepage
Cited by
Cited by
Deciding parity games in quasipolynomial time
CS Calude, S Jain, B Khoussainov, W Li, F Stephan
STOC 2017 - 49th Symposium on Theory of Computing (Best Paper STOC 2017 …, 2017
Randomness, relativization and Turing degrees
A Nies, F Stephan, SA Terwijn
The Journal of Symbolic Logic 70 (2), 515-535, 2005
Kolmogorov complexity and the recursion theorem
B Kjos-Hanssen, W Merkle, F Stephan
Transactions of the American Mathematical Society 363 (10), 5465-5480, 2011
Automatic structures: richness and limitations
B Khoussainov, A Nies, S Rubin, F Stephan
Logical Methods in Computer Science 3, 2007
Trivial reals
RG Downey, DR Hirschfeldt, A Nies, F Stephan
Proceedings of the 7th and 8th Asian Logic Conferences, 103-131, 2003
Approximable sets
R Beigel, M Kummer, F Stephan
Information and Computation 120 (2), 304-314, 1995
Using random sets as oracles
DR Hirschfeldt, A Nies, F Stephan
Journal of the London Mathematical Society 75 (3), 610-622, 2007
An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space
J Fearnley, S Jain, B de Keijzer, S Schewe, F Stephan, D Wojtczak
International Journal on Software Tools for Technology Transfer 21 (3), 325-349, 2019
Language learning from texts: mindchanges, limited memory and monotonicity
E Kinber, F Stephan
Information and Computation 123 (2), 224-241, 1995
Kolmogorov–Loveland randomness and stochasticity
W Merkle, JS Miller, A Nies, J Reimann, F Stephan
Annals of Pure and Applied Logic 138 (1-3), 183-210, 2006
A cohesive set which is not high
C Jockusch, F Stephan
Mathematical Logic Quarterly 39 (1), 515-530, 1993
Automatic linear orders and trees
B Khoussainov, S Rubin, F Stephan
ACM Transactions on Computational Logic (TOCL) 6 (4), 675-700, 2005
Martin-Löf random and PA-complete sets
F Stephan
Proceedings of ASL Logic Colloquium 2002, ASL Lecture Notes in Logic 27, 342-348, 2006
Lowness for the class of Schnorr random reals
B Kjos-Hanssen, A Nies, F Stephan
SIAM Journal on Computing 35 (3), 647-657, 2005
Extremes in the degrees of inferability
L Fortnow, W Gasarch, S Jain, E Kinber, M Kummer, S Kurtz, ...
Annals of pure and applied logic 66 (3), 231-276, 1994
On the structure of degrees of inferability
M Kummer, F Stephan
Journal of Computer and System Sciences 52 (2), 214-238, 1996
Lowness properties and approximations of the jump
S Figueira, A Nies, F Stephan
Annals of Pure and Applied Logic 152 (1-3), 51-66, 2008
When unlearning helps
G Baliga, J Case, W Merkle, F Stephan, R Wiehagen
Information and Computation 206, 694-709, 2008
On the computational complexity of some classical equivalence relations on Boolean functions
B Borchert, D Ranjan, F Stephan
Theory of Computing Systems 31 (6), 679-693, 1998
Hausdorff dimension in exponential time
K Ambos-Spies, W Merkle, J Reimann, F Stephan
Proceedings 16th Annual IEEE Conference on Computational Complexity, 210-217, 2001
The system can't perform the operation now. Try again later.
Articles 1–20