76 citations · 207 across the 31 of their papers we have counts for
4 papers · 1 filter
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…