11 citations · 15 across the 8 of their papers we have counts for
12 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…
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…
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…
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…
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…
Automatic functions, linear time and learning
John Case, Sanjay Jain, Samuel Seah +1
The present work determines the exact nature of {\em linear time computable} notions which characterise automatic functions (those whose graphs are recognised by a finite automaton…