F. Stephan

activity

20072022

most citedKolmogorov complexity and the Recursion Theorem

76 citations · 207 across the 31 of their papers we have counts for

collaborators

Showing 2020Show all

3 papers · 1 filter

cs.LO2020

Learnability and Positive Equivalence Relations

David Belanger, Ziyuan Gao, Sanjay Jain +2

Prior work of Gavryushkin, Khoussainov, Jain and Stephan investigated what algebraic structures can be realised in worlds given by a positive (= recursively enumerable) equivalence…

math.LO2020

members of thin $Π_{1}^{0}$ classes and generic degrees

Frank Stephan, Guohua Wu, Bowen Yuan

A $Π_{1}^{0}$ class $P$ is thin if every $Π_{1}^{0}$ subclass $Q$ of $P$ is the intersection of $P$ with some clopen set. In 1993, Cenzer, Downey, Jockusch and Shore initiated the…

cs.DS2020

A Faster Exact Algorithm to Count X3SAT Solutions

Gordon Hoi, Sanjay Jain, Frank Stephan

The Exact Satisfiability problem, XSAT, is defined as the problem of finding a satisfying assignment to a formula in CNF such that there is exactly one literal in each clause assig…

Learnability and Positive Equivalence Relations

members of thin Π10​ classes and generic degrees

A Faster Exact Algorithm to Count X3SAT Solutions

members of thin $Π_{1}^{0}$ classes and generic degrees