BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Bjørn Kjos-Hanssen

Bjørn Kjos-Hanssen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.LOFormal Languages and Automata TheoryLogic in Computer ScienceComputational Complexitymath.COComputation and Languagemath.CAmath.FAmath.PRq-fin.PR

Catalog footprint

What is connected

43works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

43 published item(s)

preprint2022arXiv

An incompressibility theorem for automatic complexity

Shallit and Wang showed that the automatic complexity $A(x)$ satisfies $A(x)\ge n/13$ for almost all $x\in{\{\mathtt{0},\mathtt{1}\}}^n$. They also stated that Holger Petersen had informed them that the constant 13 can be reduced to 7. Here we show that it can be reduced to $2+ε$ for any $ε>0$. The result also applies to nondeterministic automatic complexity $A_N(x)$. In that setting the result is tight inasmuch as $A_N(x)\le n/2+1$ for all $x$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Maximal automatic complexity and context-free languages

Let $A_N$ denote nondeterministic automatic complexity and \[ L_{k,c}=\{x\in [k]^* : A_N(x)> |x|/c\}. \] In particular, $L_{k,2}$ is the language of all $k$-ary words for which $A_N$ is maximal, while $L_{k,3}$ gives a rough dividing line between complex and simple. Let $\mathbf{CFL}$ denote the complexity class consisting of all context-free languages. While it is not known that $L_{2,2}$ is infinite, Kjos-Hanssen (2017) showed that $L_{3,2}$ is $\mathbf{CFL}$-immune but not $\mathbf{coCFL}$-immune. We complete the picture by showing that $L_{3,2}\not\in\mathbf{coCFL}$. Turning to Boolean circuit complexity, we show that $L_{2,3}$ is $\mathbf{SAC}^0$-immune and $\mathbf{SAC}^0$-coimmune. Here $\mathbf{SAC}^0$ denotes the complexity class consisting of all languages computed by (non-uniform) constant-depth circuits with semi-unbounded fanin. As for arithmetic circuits, we show that $\{x:A_N(x)>1\}\not\in\oplus\mathbf{SAC}^0$. In particular, $\mathbf{SAC}^0\not\subseteq\oplus \mathbf{SAC}^0$, which resolves an open implication from the Complexity Zoo.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Strong Medvedev reducibilities and the KL-randomness problem

While it is not known whether each real that is Kolmogorov-Loveland random is Martin-Löf random, i.e., whether $\mathrm{KLR}\subseteq\mathrm{MLR}$, Kjos-Hanssen and Webb (2021) showed that $\mathrm{MLR}$ is truth-table Medvedev reducible ($\le_{s,tt}$) to $\mathrm{KLR}$. They did this by studying a natural class Either(MLR) and showing that $\mathrm{MLR}\le_{s,tt}\mathrm{Either(MLR)}\supseteq\mathrm{KLR}$. We show that Degtev's stronger reducibilities (positive and linear) do not suffice for the reduction of MLR to Either(MLR), and some related results.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A tractable case of the Turing automorphism problem: bi-uniformly $E_0$-invariant Cantor homeomorphisms

A function $F:2^ω\to 2^ω$ is an $E_0$-isomorphism if for all $x,y\in 2^ω$, we have $xE_0y\iff f(x)E_0 f(y)$, where $xE_0y\iff(\exists a)(\forall n\ge b) x(n)=y(n)$. If such witnesses $a$ for $xE_0 y$ and for $f(x)E_0 f(y)$ depend on each other but not on $x$, $y$, then $F$ is called bi-uniform. It is shown that a homeomorphism of Cantor space which is a bi-uniform $E_0$-isomorphism can induce only the trivial automorphism of the Turing degrees.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Automatic complexity of shift register sequences

Let $x$ be an $m$-sequence, a maximal length sequence produced by a linear feedback shift register. We show that $x$ has maximal subword complexity function in the sense of Allouche and Shallit. We show that this implies that the nondeterministic automatic complexity $A_N(x)$ is close to maximal: $n/2-A_N(x)=O(\log^2n)$, where $n$ is the length of $x$. In contrast, Hyde has shown $A_N(y)\le n/2+1$ for all sequences $y$ of length $n$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

From eventually different functions to pandemic numberings

A function is strongly non-recursive (SNR) if it is eventually different from each recursive function. We obtain hierarchy results for the mass problems associated with computing such functions with varying growth bounds. In particular, there is no least and no greatest Muchnik degree among those of the form SNR$_f$ consisting of SNR functions bounded by varying recursive bounds $f$. We show that the connection between SNR functions and canonically immune sets is, in a sense, as strong as that between DNR (diagonally non-recursive) functions and effectively immune sets. Finally, we introduce pandemic numberings, a set-theoretic dual to immunity.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Nondeterministic automatic complexity of overlap-free and almost square-free words

Shallit and Wang studied deterministic automatic complexity of words. They showed that the automatic Hausdorff dimension $I(\mathbf t)$ of the infinite Thue word satisfies $1/3\le I(\mathbf t)\le 2/3$. We improve that result by showing that $I(\mathbf t)\ge 1/2$. For nondeterministic automatic complexity we show $I(\mathbf t)=1/2$. We prove that such complexity $A_N$ of a word $x$ of length $n$ satisfies $A_N(x)\le b(n):=\lfloor n/2\rfloor + 1$. This enables us to define the complexity deficiency $D(x)=b(n)-A_N(x)$. If $x$ is square-free then $D(x)=0$. If $x$ almost square-free in the sense of Fraenkel and Simpson, or if $x$ is a strongly cube-free binary word such as the infinite Thue word, then $D(x)\le 1$. On the other hand, there is no constant upper bound on $D$ for strongly cube-free words in a ternary alphabet, nor for cube-free words in a binary alphabet. The decision problem whether $D(x)\ge d$ for given $x$, $d$ belongs to $NP\cap E$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the complexity of automatic complexity

Generalizing the notion of automatic complexity of individual strings due to Shallit and Wang, we define the automatic complexity $A(E)$ of an equivalence relation $E$ on a finite set $S$ of strings. We prove that the problem of determining whether $A(E)$ equals the number $|E|$ of equivalence classes of $E$ is $\mathsf{NP}$-complete. The problem of determining whether $A(E) = |E| + k$ for a fixed $k\ge 1$ is complete for the second level of the Boolean hierarchy for $\mathsf{NP}$, i.e., $\mathsf{BH}_2$-complete. Let $L$ be the language consisting of all strings of maximal nondeterministic automatic complexity. We characterize the complexity of infinite subsets of $L$ by showing that they can be co-context-free but not context-free, i.e., $L$ is $\mathsf{CFL}$-immune, but not $\mathsf{coCFL}$-immune. We show that for each $ε>0$, $L_ε\not\in\mathsf{coCFL}$, where $L_ε$ is the set of all strings whose deterministic automatic complexity $A(x)$ satisfies $A(x)\ge |x|^{1/2-ε}$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Few paths, fewer words: model selection with automatic structure functions

We consider the problem of finding an optimal statistical model for a given binary string. Following Kolmogorov, we use structure functions. In order to get concrete results, we replace Turing machines by finite automata and Kolmogorov complexity by Shallit and Wang's automatic complexity. The $p$-value of a model for given data $x$ is the probability that there exists a model with as few states, accepting as few words, fitting uniformly randomly selected data $y$. Deterministic and nondeterministic automata can give different optimal models. For $x=011\, 110\, 110\, 11$, the best deterministic model has $p$-value $0.3$, whereas the best nondeterministic model has $p$-value $0.04$. In the nondeterministic case, counting paths and counting words can give different optimal models. For $x=01100\, 01000$, the best path-counting model has $p$-value $0.79$, whereas the best word-counting model has $p$-value $0.60$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Google distance between words

Cilibrasi and Vitanyi have demonstrated that it is possible to extract the meaning of words from the world-wide web. To achieve this, they rely on the number of webpages that are found through a Google search containing a given word and they associate the page count to the probability that the word appears on a webpage. Thus, conditional probabilities allow them to correlate one word with another word's meaning. Furthermore, they have developed a similarity distance function that gauges how closely related a pair of words is. We present a specific counterexample to the triangle inequality for this similarity distance function.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Algorithmic randomness for Doob's martingale convergence theorem in continuous time

We study Doob's martingale convergence theorem for computable continuous time martingales on Brownian motion, in the context of algorithmic randomness. A characterization of the class of sample points for which the theorem holds is given. Such points are given the name of Doob random points. It is shown that a point is Doob random if its tail is computably random in a certain sense. Moreover, Doob randomness is strictly weaker than computable randomness and is incomparable with Schnorr randomness.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Arithmetic complexity via effective names for random sequences

We investigate enumerability properties for classes of sets which permit recursive, lexicographically increasing approximations, or left-r.e. sets. In addition to pinpointing the complexity of left-r.e. Martin-Löf, computably, Schnorr, and Kurtz random sets, weakly 1-generics and their complementary classes, we find that there exist characterizations of the third and fourth levels of the arithmetic hierarchy purely in terms of these notions. More generally, there exists an equivalence between arithmetic complexity and existence of numberings for classes of left-r.e. sets with shift-persistent elements. While some classes (such as Martin-Löf randoms and Kurtz non-randoms) have left-r.e. numberings, there is no canonical, or acceptable, left-r.e. numbering for any class of left-r.e. randoms. Finally, we note some fundamental differences between left-r.e. numberings for sets and reals.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Effective dimension of points visited by Brownian motion

We consider the individual points on a Martin-Löf random path of Brownian motion. We show (1) that Khintchine's law of the iterated logarithm holds at almost all points; and (2) there exist points (besides the trivial example of the origin) having effective dimension $<1$. The proof of (1) shows that for almost all times $t$, the path $f$ is Martin-Löf random relative to $t$ and so the effective dimension of $(t,f(t))$ is 2.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Finding subsets of positive measure

An important theorem of geometric measure theory (first proved by Besicovitch and Davies for Euclidean space) says that every analytic set of non-zero $s$-dimensional Hausdorff measure $\mathcal H^s$ contains a closed subset of non-zero (and indeed finite) $\mathcal H^s$-measure. We investigate the question how hard it is to find such a set, in terms of the index set complexity, and in terms of the complexity of the parameter needed to define such a closed set. Among other results, we show that given a (lightface) $Σ^1_1$ set of reals in Cantor space, there is always a $Π^0_1(\mathcal{O})$ subset on non-zero $\mathcal H^s$-measure definable from Kleene's $\mathcal O$. On the other hand, there are $Π^0_2$ sets of reals where no hyperarithmetic real can define a closed subset of non-zero measure.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

How much randomness is needed for statistics?

In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure $λ$, a choice needs to be made. One approach is to allow randomness tests to access the measure $λ$ as an oracle (which we call the "classical approach"). The other approach is the opposite one, where the randomness tests are completely effective and do not have access to the information contained in $λ$ (we call this approach "Hippocratic"). While the Hippocratic approach is in general much more restrictive, there are cases where the two coincide. The first author showed in 2010 that in the particular case where the notion of randomness considered is Martin-Löf randomness and the measure $λ$ is a Bernoulli measure, classical randomness and Hippocratic randomness coincide. In this paper, we prove that this result no longer holds for other notions of randomness, namely computable randomness and stochasticity.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Kolmogorov complexity and strong approximation of Brownian motion

Brownian motion and scaled and interpolated simple random walk can be jointly embedded in a probability space in such a way that almost surely the $n$-step walk is within a uniform distance $O(n^{-1/2}\log n)$ of the Brownian path for all but finitely many positive integers $n$. Almost surely this $n$-step walk will be incompressible in the sense of Kolmogorov complexity, and all {Martin-Löf random} paths of Brownian motion have such an incompressible close approximant. This strengthens a result of Asarin, who obtained the bound $O(n^{-1/6} \log n)$. The result cannot be improved to $o(n^{-1/2}{\sqrt{\log n}})$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Kolmogorov complexity and the Recursion Theorem

Several classes of DNR functions are characterized in terms of Kolmogorov complexity. In particular, a set of natural numbers A can wtt-compute a DNR function iff there is a nontrivial recursive lower bound on the Kolmogorov complexity of the initial segments of A. Furthermore, A can Turing compute a DNR function iff there is a nontrivial A-recursive lower bound on the Kolmogorov complexity of the initial segements of A. A is PA-complete, that is, A can compute a {0,1}-valued DNR function, iff A can compute a function F such that F(n) is a string of length n and maximal C-complexity among the strings of length n. A solves the halting problem iff A can compute a function F such that F(n) is a string of length n and maximal H-complexity among the strings of length n. Further characterizations for these classes are given. The existence of a DNR function in a Turing degree is equivalent to the failure of the Recursion Theorem for this degree; thus the provided results characterize those Turing degrees in terms of Kolmogorov complexity which do no longer permit the usage of the Recursion Theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Lowness notions, measure and domination

We show that positive measure domination implies uniform almost everywhere domination and that this proof translates into a proof in the subsystem WWKL$_0$ (but not in RCA$_0$) of the equivalence of various Lebesgue measure regularity statements introduced by Dobrinen and Simpson. This work also allows us to prove that low for weak $2$-randomness is the same as low for Martin-Löf randomness (a result independently obtained by Nies). Using the same technique, we show that $\leq_{LR}$ implies $\leq_{LK}$, generalizing the fact that low for Martin-Löf randomness implies low for $K$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Martin-Löf randomness and Galton-Watson processes

The members of Martin-Löf random closed sets under a distribution studied by Barmpalias et al. are exactly the infinite paths through Martin-Löf random Galton--Watson trees with survival parameter $\frac{2}{3}$. To be such a member, a sufficient condition is to have effective Hausdorff dimension strictly greater than $γ=\log_2 \frac{3}{2}$, and a necessary condition is to have effective Hausdorff dimension greater than or equal to $γ$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Numberings and randomness

We prove various results on effective numberings and Friedberg numberings of families related to algorithmic randomness. The family of all Martin-Löf random left-computably enumerable reals has a Friedberg numbering, as does the family of all $Π^0_1$ classes of positive measure. On the other hand, the $Π^0_1$ classes contained in the Martin-Löf random reals do not even have an effective numbering, nor do the left-c.e. reals satisfying a fixed randomness constant. For $Π^0_1$ classes contained in the class of reals satisfying a fixed randomness constant, we prove that at least an effective numbering exists.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On a conjecture of Dobrinen and Simpson concerning almost everywhere domination

The notions of almost everywhere (a.e.) domination and its uniform version were introduced and studied in reverse mathematics. This paper studies these notions from a recursion-theoretic point of view and explore their connections to notions such as randomness and genericity. It is shown that if $Z$ is a.e. dominating then each $1$-$Z$-random is $2$-random. In other words, $0'\leq_{\rm LR} Z$ for every a.e. dominating $Z$, where ${\rm LR}$ denotes low-for-random reducibility. Other results and corollaries are also given.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Self-embeddings of computable trees

We divide the class of infinite computable trees into three types. For the first and second types, $0'$ computes a nontrivial self-embedding while for the third type $0''$ computes a nontrivial self-embedding. These results are optimal and we obtain partial results concerning the complexity of nontrivial self-embeddings of infinite computable trees considered up to isomorphism. We show that every infinite computable tree must have either an infinite computable chain or an infinite $Π^0_1$ antichain. This result is optimal and has connections to the program of reverse mathematics.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The probability distribution as a computational resource for randomness testing

When testing a set of data for randomness according to a probability distribution that depends on a parameter, access to this parameter can be considered as a computational resource. We call a randomness test Hippocratic if it is not permitted to access this resource. In these terms, we show that for Bernoulli measures $μ_p$, $0\le p\le 1$ and the Martin-Löf randomness model, Hippocratic randomness of a set of data is the same as ordinary randomness. The main idea of the proof is to first show that from Hippocrates-random data one can Turing compute the parameter $p$. However, we show that there is no single Hippocratic randomness test such that passing the test implies computing $p$, and in particular there is no universal Hippocratic randomness test.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs

We study the reverse mathematics and computability-the\-o\-re\-tic strength of (stable) Ramsey's Theorem for pairs and the related principles COH and DNR. We show that SRT$^2_2$ implies DNR over RCA$_0$ but COH does not, and answer a question of Mileti by showing that every computable stable $2$-coloring of pairs has an incomplete $Δ^0_2$ infinite homogeneous set. We also give some extensions of the latter result, and relate it to potential approaches to showing that SRT$^2_2$ does not imply RT$^2_2$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Effective Banach spaces

This thesis addresses Pour-El and Richards' fourth question from their book "Computability in analysis and physics", concerning the relation between higher order recursion theory and computability in analysis. Among other things it is shown that there is a computability structure that is uncountable. The example given is a structure on the Banach space of bounded linear operators on the set of almost periodic functions.

0 citations0 reviewsNo code linkedOpen access