B. Kjos-Hanssen

activity

20092026

most citedKolmogorov complexity and the Recursion Theorem

76 citations · 440 across the 53 of their papers we have counts for

collaborators

Showing 2026Show all

4 papers · 1 filter

quant-ph2026

Quantum Černý complexity of binary words

Pui Hang Lee, Pui-Yee Lee, Bjørn Kjos-Hanssen

We introduce the quantum Černý complexity $qc (w)$ of a binary word $w$ : the least dimension $d$ for which there exist quantum channels $A_{0}, A_{1}$ on $d \times d$ density mat…

cs.DM2026

The exact asymptotic constant in the metric dimension of Jaccard space

Bjørn Kjos-Hanssen

Let $X$ be a finite set with $∣ X ∣ = n$ and let $Jac (a, b) = ∣ a △ b ∣/∣ a \cup b ∣$ be the Jaccard distance on the power set $2^{X}$ . Lladser and Paradise recently proved t…

cs.FL2026

Exact versus unique nondeterministic automatic complexity

Bjørn Kjos-Hanssen, Travis Rivera Petit

The exact nondeterministic automatic complexity $A_{N e} (x)$ of a word $x$ is the minimum number of states of a nondeterministic finite automaton that accepts $x$ and no other word…

cs.FL2026

Every string has probabilistic automatic complexity at most three

Bjørn Kjos-Hanssen

Gill (arXiv:2402.13376) introduced the probabilistic automatic complexity $A_{P} (w)$ of a finite string $w$ : the least number of states of a probabilistic finite automaton (PFA) for…