76 citations · 207 across the 31 of their papers we have counts for
36 papers
A Computation Model with Automatic Functions and Relations as Primitive Operations
Ziyuan Gao, Sanjay Jain, Li Zeyong +2
Prior work of Hartmanis and Simon (Hartmanis and Simon, 1974) and Floyd and Knuth (Floyd and Knuth, 1990) investigated what happens if a device uses primitive steps more natural th…
Addition Machines, Automatic Functions and Open Problems of Floyd and Knuth
Sanjay Jain, Xiaodong Jia, Ammar Fathin Sabili +1
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…
Alternating Automatic Register Machines
Ziyuan Gao, Sanjay Jain, Zeyong Li +2
This paper introduces and studies a new model of computation called an Alternating Automatic Register Machine (AARM). An AARM possesses the basic features of a conventional registe…
Ordered Semiautomatic Rings with Applications to Geometry
Ziyuan Gao, Sanjay Jain, Ji Qi +3
The present work looks at semiautomatic rings with automatic addition and comparisons which are dense subrings of the real numbers and asks how these can be used to represent geome…
Improved Algorithms for the General Exact Satisfiability Problem
Gordon Hoi, Frank Stephan
The Exact Satisfiability problem asks if we can find a satisfying assignment to each clause such that exactly one literal in each clause is assigned , while the rest are all ass…
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…
members of thin classes and generic degrees
Frank Stephan, Guohua Wu, Bowen Yuan
A class is thin if every subclass of is the intersection of with some clopen set. In 1993, Cenzer, Downey, Jockusch and Shore initiated the…
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…
A Fast Exponential Time Algorithm for Max Hamming Distance X3SAT
Gordon Hoi, Sanjay Jain, Frank Stephan
X3SAT is the problem of whether one can satisfy a given set of clauses with up to three literals such that in every clause, exactly one literal is true and the others are false. A…
On the order dimension of locally countable partial orderings
Kojiro Higuchi, Steffen Lempp, Diip Raghavan +1
We show that the order dimension of the partial order of all finite subsets of under set inclusion is whenever is an infinite cardinal. We also…
Randomness and initial segment complexity for probability measures
Andre Nies, Frank Stephan
We study algorithmic randomness properties for probability measures on Cantor space. We say that a measure on the space of infinite bit sequences is ML absolutely continuous if…
Random Subgroups of Rationals
Ziyuan Gao, Sanjay Jain, Bakhadyr Khoussainov +4
This paper introduces and studies a notion of \emph{algorithmic randomness} for subgroups of rationals. Given a randomly generated additive subgroup of rationals, two main…
The isomorphism problem for tree-automatic ordinals with addition
Sanjay Jain, Bakhadyr Khoussainov, Philipp Schlicht +1
This paper studies tree-automatic ordinals (or equivalently, well-founded linearly ordered sets) together with the ordinal addition operation +. Informally, these are ordinals such…
Subrecursive Approximations of Irrational Numbers by Variable Base Sums
Ivan Georgiev, Lars Kristiansen, Frank Stephan
There are numerous ways to represent real numbers. We may use, e.g., Cauchy sequences, Dedekind cuts, numerical base-10 expansions, numerical base-2 expansions and continued fracti…
Equivalences between learning of data and probability distributions, and their applications
George Barmpalias, Nan Fang, Frank Stephan
Algorithmic learning theory traditionally studies the learnability of effective infinite binary sequences (reals), while recent work by [Vitanyi and Chater, 2017] and [Bienvenu et…
Covering the recursive sets
Bjørn Kjos-Hanssen, Frank Stephan, Sebastiaan A. Terwijn
We give solutions to two of the questions in a paper by Brendle, Brooke-Taylor, Ng and Nies. Our examples derive from a 2014 construction by Khan and Miller as well as new direct c…
Algorithmic learning of probability distributions from random data in the limit
George Barmpalias, Frank Stephan
We study the problem of identifying a probability distribution for some given randomly sampled data in the limit, in the context of algorithmic learning theory as proposed recently…
Closure of resource-bounded randomness notions under polynomial time permutations
Andre Nies, Frank Stephan
An infinite bit sequence is called recursively random if no computable strategy betting along the sequence has unbounded capital. It is well-known that the property of recursive ra…
An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space
John Fearnley, Sanjay Jain, Sven Schewe +2
Parity games play an important role in model checking and synthesis. In their paper, Calude et al. have shown that these games can be solved in quasi-polynomial time. We show that…
How to verify computation with a rational network
Sanjay Jain, Prateek Saxena, Frank Stephan +1
The present paper introduces a practical protocol for provably secure, outsourced computation. Our protocol minimizes overhead for verification by requiring solutions to withstand…
Depth, Highness and DNR degrees
Philippe Moser, Frank Stephan
We study Bennett deep sequences in the context of recursion theory; in particular we investigate the notions of O(1)-deepK, O(1)-deepC , order-deep K and order-deep C sequences. Ou…
Combining Models of Approximation with Partial Learning
Ziyuan Gao, Frank Stephan, Sandra Zilles
In Gold's framework of inductive inference, the model of partial learning requires the learner to output exactly one correct index for the target object and only the target object…
Partial functions and domination
C. T. Chong, Gordon Hoi, Frank Stephan +1
The current work introduces the notion of pdominant sets and studies their recursion-theoretic properties. Here a set A is called pdominant iff there is a partial A-recursive funct…
Higher Kurtz randomness
Bjørn Kjos-Hanssen, André Nies, Frank Stephan +1
A real is -Kurtz random (-Kurtz random) if it is in no closed null set ( set). We show that there is a cone of -Kurtz random hyperdegrees. W…