Frank Stephan
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Frank Stephan has a total of 274 co-authors. Here are the top co-authors by number of shared publications:
Sanjay Jain
56 shared publications- Sanjay Jain
School of Computing National University of Singapore
54 shared publications - André Nies
University of Auckland
20 shared publications - Arun Sharma
Queensland University of Technology
20 shared publications John Case
University of Delaware
20 shared publicationsEric Martin
The University of New South Wales
15 shared publications
Latest Publications
- Open Access
- 22 August 2026
- Published by Elsevier in SSRN Electronic Journal
An Improved Algorithm for Sparse Instances of SAT
We show that the CNF satisfiability problem (SAT) can be solved in time O(1.1199^(d-2)n), where d is either the maximum number of occurrences of any variable or the average number of occurrences of all variables if no variable occurs at most once. This improves upon the known upper bound of O(1.1279^(d-2)n) by Wahlstrom (SAT 2005) and O(1.1238^(d-2)n) by Peng and Xiao (IJCAI 2023). For d <= 4, our algorithm improves upon previous results. Our main technical result is an algorithm that runs in O(1.1199^n) for 3-occur-SAT, a restricted instance of SAT where all variables have at most three occurrences. Through deeper case analysis and a reduction rule that allows us to resolve many variables under a relatively broad criterion, we circumvent the main bottlenecks in previous algorithms.
- 22 August 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessAn Improved Algorithm for Sparse Instances of SAT
We show that the CNF satisfiability problem (SAT) can be solved in time O(1.1199^(d-2)n), where d is either the maximum number of occurrences of any variable or the average number of occurrences of all variables if no variable occurs at most once. This improves upon the known upper bound of O(1.1279^(d-2)n) by Wahlstrom (SAT 2005) and O(1.1238^(d-2)n) by Peng and Xiao (IJCAI 2023). For d <= 4, our algorithm improves upon previous results. Our main technical result is an algorithm that runs in O(1.1199^n) for 3-occur-SAT, a restricted instance of SAT where all variables have at most three occurrences. Through deeper case analysis and a reduction rule that allows us to resolve many variables under a relatively broad criterion, we circumvent the main bottlenecks in previous algorithms.
- Open Access
- 16 July 2026
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- p. 1-15
ON TREES WITHOUT HYPERIMMUNE BRANCHES
The current work includes a result announced in the year 2012 which was unproven for 10 years. The result shows that there is a co-r.e. tree with uncountably many infinite branches such that the nonisolated infinite branches of the constructed tree are all nonrecursive, generalised low, and hyperimmune-free and form a perfect tree. This article is the journal version of two conference articles from 2012 and 2022; the article contains the main result proved in 2022 and also the other major results from 2012.
- 16 July 2026
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- p. 1-15
Open AccessON TREES WITHOUT HYPERIMMUNE BRANCHES
The current work includes a result announced in the year 2012 which was unproven for 10 years. The result shows that there is a co-r.e. tree with uncountably many infinite branches such that the nonisolated infinite branches of the constructed tree are all nonrecursive, generalised low, and hyperimmune-free and form a perfect tree. This article is the journal version of two conference articles from 2012 and 2022; the article contains the main result proved in 2022 and also the other major results from 2012.
- Open Access
Languages of Words of Low Automatic Complexity Are Hard to Compute
The automatic complexity of a finite word (string) is an analogue for finite automata of Sipser's distinguishing complexity (1983) and was introduced by Shallit and Wang (2001). For a finite alphabet $Σ$ of at least two elements, we consider the non-deterministic automatic complexity given by exactly - yet not necessarily uniquely - accepting automata: a word $x \in Σ^*$ has exact non-deterministic automatic complexity $k \in \mathbb{N}$ if there exists a non-deterministic automaton of $k$ states which accepts $x$ while rejecting every other word of the same length as $x$, and no automaton of fewer states has this property. Importantly, and in contrast to the classical notion, the witnessing automaton may have multiple paths of computation accepting $x$. We denote this measure of complexity by $A_{Ne}$, and study a class of languages of low $A_{Ne}$-complexity defined as $L_q = \{ \, x \in Σ^* : A_{Ne}(x) < q|x| \, \}$, which is parameterised by rationals $q \in (0,1/2)$ (generalising a class of sets first studied by Kjos-Hanssen). We show that for every $q \in (0,1/2)$, this class is neither context-free nor recognisable by certain Boolean circuits. In the process, we answer an open question of Kjos-Hanssen quantifying the complexity of $L_{1/3}$ in terms of Boolean circuits, and also prove the Shannon effect for $A_{Ne}$.Open AccessLanguages of Words of Low Automatic Complexity Are Hard to Compute
The automatic complexity of a finite word (string) is an analogue for finite automata of Sipser's distinguishing complexity (1983) and was introduced by Shallit and Wang (2001). For a finite alphabet $Σ$ of at least two elements, we consider the non-deterministic automatic complexity given by exactly - yet not necessarily uniquely - accepting automata: a word $x \in Σ^*$ has exact non-deterministic automatic complexity $k \in \mathbb{N}$ if there exists a non-deterministic automaton of $k$ states which accepts $x$ while rejecting every other word of the same length as $x$, and no automaton of fewer states has this property. Importantly, and in contrast to the classical notion, the witnessing automaton may have multiple paths of computation accepting $x$. We denote this measure of complexity by $A_{Ne}$, and study a class of languages of low $A_{Ne}$-complexity defined as $L_q = \{ \, x \in Σ^* : A_{Ne}(x) < q|x| \, \}$, which is parameterised by rationals $q \in (0,1/2)$ (generalising a class of sets first studied by Kjos-Hanssen). We show that for every $q \in (0,1/2)$, this class is neither context-free nor recognisable by certain Boolean circuits. In the process, we answer an open question of Kjos-Hanssen quantifying the complexity of $L_{1/3}$ in terms of Boolean circuits, and also prove the Shannon effect for $A_{Ne}$. - Open Access
- 2 June 2025
- Published by Cambridge University Press (CUP) in Journal of the Australian Mathematical Society
- Vol. 119 (1) , 61-81
IMPROVED LOWER BOUNDS FOR STRONG n-CONJECTURES
The well-known $abc$ -conjecture concerns triples $(a,b,c)$ of nonzero integers that are coprime and satisfy ${a+b+c=0}$ . The strong n-conjecture is a generalisation to n summands where integer solutions of the equation ${a_1 + \cdots + a_n = 0}$ are considered such that the $a_i$ are pairwise coprime and satisfy a certain subsum condition. Ramaekers studied a variant of this conjecture with a slightly different set of conditions. He conjectured that in this setting the limit superior of the so-called qualities of the admissible solutions equals $1$ for any n. In this paper, we follow results of Konyagin and Browkin. We restrict to a smaller, and thus more demanding, set of solutions, and improve the known lower bounds on the limit superior: for ${n \geq 6}$ we achieve a lower bound of $\frac 54$ ; for odd $n \geq 5$ we even achieve $\frac 53$ . In particular, Ramaekers’ conjecture is false for every ${n \ge 5}$ .- 2 June 2025
- Published by Cambridge University Press (CUP) in Journal of the Australian Mathematical Society
- Vol. 119 (1) , 61-81
Open AccessIMPROVED LOWER BOUNDS FOR STRONG n-CONJECTURES
The well-known $abc$ -conjecture concerns triples $(a,b,c)$ of nonzero integers that are coprime and satisfy ${a+b+c=0}$ . The strong n-conjecture is a generalisation to n summands where integer solutions of the equation ${a_1 + \cdots + a_n = 0}$ are considered such that the $a_i$ are pairwise coprime and satisfy a certain subsum condition. Ramaekers studied a variant of this conjecture with a slightly different set of conditions. He conjectured that in this setting the limit superior of the so-called qualities of the admissible solutions equals $1$ for any n. In this paper, we follow results of Konyagin and Browkin. We restrict to a smaller, and thus more demanding, set of solutions, and improve the known lower bounds on the limit superior: for ${n \geq 6}$ we achieve a lower bound of $\frac 54$ ; for odd $n \geq 5$ we even achieve $\frac 53$ . In particular, Ramaekers’ conjecture is false for every ${n \ge 5}$ . - Open Access
Strong $n$-conjectures over rings of integers
We study diophantine equations of the form ${a_1 + \ldots + a_n = 0}$ where the $a_i$'s are assumed to be coprime and to satisfy certain subsum conditions. We are interested in the limit superior of the qualities of the admissible solutions of these equations, a question that in the case ${n = 3}$ is closely related to the famous $abc$-conjecture. In a previous article, we studied multiple versions of this problem over the ring of rational integers, summarising known results and proving stronger lower bounds. In this article we extend our work to the rings of the Gaussian integers and the Hurwitz quaternions, where a somewhat different picture emerges. In particular, we establish much stronger lower bounds on qualities than for the rational integers.Open AccessStrong $n$-conjectures over rings of integers
We study diophantine equations of the form ${a_1 + \ldots + a_n = 0}$ where the $a_i$'s are assumed to be coprime and to satisfy certain subsum conditions. We are interested in the limit superior of the qualities of the admissible solutions of these equations, a question that in the case ${n = 3}$ is closely related to the famous $abc$-conjecture. In a previous article, we studied multiple versions of this problem over the ring of rational integers, summarising known results and proving stronger lower bounds. In this article we extend our work to the rings of the Gaussian integers and the Hurwitz quaternions, where a somewhat different picture emerges. In particular, we establish much stronger lower bounds on qualities than for the rational integers. - Open Access
Classifying different criteria for learning algebraic structures
In the last years there has been a growing interest in the study of learning problems associated with algebraic structures. The framework we use models the scenario in which a learner is given larger and larger fragments of a structure from a given target family and is required to output an hypothesis about the structure's isomorphism type. So far researchers focused on $\mathbf{Ex}$-learning, in which the learner is asked to eventually stabilize to the correct hypothesis, and on restrictions where the learner is allowed to change the hypothesis a fixed number of times. Yet, other learning paradigms coming from classical algorithmic learning theory remained unexplored. We study the "learning power" of such criteria, comparing them via descriptive-set-theoretic tools thanks to the novel notion of $E$-learnability. The main outcome of this paper is that such criteria admit natural syntactic characterizations in terms of infinitary formulas analogous to the one given for $\mathbf{Ex}$-learning in [6]. Such characterizations give a powerful method to understand whether a family of structure is learnable with respect to the desired criterion.
Open AccessClassifying different criteria for learning algebraic structures
In the last years there has been a growing interest in the study of learning problems associated with algebraic structures. The framework we use models the scenario in which a learner is given larger and larger fragments of a structure from a given target family and is required to output an hypothesis about the structure's isomorphism type. So far researchers focused on $\mathbf{Ex}$-learning, in which the learner is asked to eventually stabilize to the correct hypothesis, and on restrictions where the learner is allowed to change the hypothesis a fixed number of times. Yet, other learning paradigms coming from classical algorithmic learning theory remained unexplored. We study the "learning power" of such criteria, comparing them via descriptive-set-theoretic tools thanks to the novel notion of $E$-learnability. The main outcome of this paper is that such criteria admit natural syntactic characterizations in terms of infinitary formulas analogous to the one given for $\mathbf{Ex}$-learning in [6]. Such characterizations give a powerful method to understand whether a family of structure is learnable with respect to the desired criterion.
- 29 February 2024
- Published by Springer Nature
- p. 257-272
A Bisection Approach to Subcubic Maximum Induced Matching
- 29 February 2024
- Published by Springer Nature
- p. 257-272
A Bisection Approach to Subcubic Maximum Induced Matching
- 12 April 2023
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 136, 135-156
Addition machines, automatic functions and open problems of Floyd and Knuth
- 12 April 2023
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 136, 135-156
Addition machines, automatic functions and open problems of Floyd and Knuth
- Open Access
String Compression in FA-Presentable Structures
We construct a FA-presentation $ψ: L \rightarrow \mathbb{N}$ of the structure $(\mathbb{N};\mathrm{S})$ for which a numerical characteristic $r(n)$ defined as the maximum number $ψ(w)$ for all strings $w \in L$ of length less than or equal to $n$ grows faster than any tower of exponents of a fixed height. This result leads us to a more general notion of a compressibility rate defined for FA-presentations of any FA-presentable structure. We show the existence of FA-presentations for the configuration space of a Turing machine and Cayley graphs of some groups for which it grows faster than any tower of exponents of a fixed height. For FA-presentations of the Presburger arithmetic $(\mathbb{N};+)$ we show that it is bounded from above by a linear function.Open AccessString Compression in FA-Presentable Structures
We construct a FA-presentation $ψ: L \rightarrow \mathbb{N}$ of the structure $(\mathbb{N};\mathrm{S})$ for which a numerical characteristic $r(n)$ defined as the maximum number $ψ(w)$ for all strings $w \in L$ of length less than or equal to $n$ grows faster than any tower of exponents of a fixed height. This result leads us to a more general notion of a compressibility rate defined for FA-presentations of any FA-presentable structure. We show the existence of FA-presentations for the configuration space of a Turing machine and Cayley graphs of some groups for which it grows faster than any tower of exponents of a fixed height. For FA-presentations of the Presburger arithmetic $(\mathbb{N};+)$ we show that it is bounded from above by a linear function. - Open Access
Addition Machines, Automatic Functions and Open Problems of Floyd and Knuth
Floyd and Knuth investigated in 1990 register machines which can add, subtract and compare integers as primitive operations. They asked whether their current bound on the number of registers for multiplying and dividing fast (running in time linear in the size of the input) can be improved and whether one can output fast the powers of two summing up to a positive integer in subquadratic time. Both questions are answered positively. Furthermore, it is shown that every function computed by only one register is automatic and that automatic functions with one input can be computed with four registers in linear time; automatic functions with a larger number of inputs can be computed with 5 registers in linear time. There is a nonautomatic function with one input which can be computed with two registers in linear time.
Open AccessAddition Machines, Automatic Functions and Open Problems of Floyd and Knuth
Floyd and Knuth investigated in 1990 register machines which can add, subtract and compare integers as primitive operations. They asked whether their current bound on the number of registers for multiplying and dividing fast (running in time linear in the size of the input) can be improved and whether one can output fast the powers of two summing up to a positive integer in subquadratic time. Both questions are answered positively. Furthermore, it is shown that every function computed by only one register is automatic and that automatic functions with one input can be computed with four registers in linear time; automatic functions with a larger number of inputs can be computed with 5 registers in linear time. There is a nonautomatic function with one input which can be computed with two registers in linear time.