Logic Blog 2021
The blog has several entries on group theory interacting with computability and wider logic, several open questions, and an entry on undecidability in physics.
Researcher profile
Andre Nies
Andre Nies contributes to research discovery and scholarly infrastructure.
ResearcherAffiliation not importedOpen to collaborate
Trust snapshot
Quick read
Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
2topics
4close collaborators
Actions
Decide how to stay connected
Identity and collaboration
How to connect with this researcher
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Open a focused conversation when the fit is right
Claim this author entity first to unlock direct invitations.
Research graph
See the researcher in context
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
Building this graph slice
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
8 published item(s)
preprint2022arXiv
Martin-Löf reducibility and cost functions
Martin-Löf (ML)-reducibility compares $K$-trivial sets by examining the Martin-Löf random sequences that compute them. We show that every $K$-trivial set is computable from a c.e.\ set of the same ML-degree. We investigate the interplay between ML-reducibility and cost functions, which are used to both measure the number of changes in a computable approximation, and the type of null sets used to capture ML-random sequences. We show that for every cost function there is a c.e.\ set ML-above the sets obeying it (called an ML-complete set for the cost function). We characterise the $K$-trivial sets computable from a fragment of the left-c.e.\ random real~$Ω$. This leads to a new characterisation of strong jump-traceability.
0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv
Logic Blog 2020
This year's blog has focused on the connections of group theory with logic and algorithms. The first post is on automata presentable groups. Then there are several posts related to topological groups, for instance Ivanov and Majcher showing that extreme amenability of closed subgroups of $S_\infty$ is a Borel property. One post due to Harrison-Trainor and Nies reviews notes by Segal on pseudofinite groups, and attempts an effective version. About 25 percent is on computability and randomness, in particular equivalence of reducibilities weaker than Turing on the K-trivials by Greenberg, Nies and Turetsky, and the effective SMB theorem in the quantum setting by Nies and Tomamichel.
0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv
Logic Blog 2019
The blog focusses on algorithmic randomness and its connections to quantum information theory, group theory and its connections to logic, and computability analogs of cardinal characteristics.
0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv
Computing from projections of random points: a dense hierarchy of subideals of the $K$-trivial degrees
We study the sets that are computable from both halves of some (Martin-Löf) random sequence, which we call \emph{$1/2$-bases}. We show that the collection of such sets forms an ideal in the Turing degrees that is generated by its c.e.\ elements. It is a proper subideal of the $K$-trivial sets. We characterise $1/2$-bases as the sets computable from both halves of Chaitin's $Ω$, and as the sets that obey the cost function $\mathbf c(x,s) = \sqrt{Ω_s - Ω_x}$. Generalising these results yields a dense hierarchy of subideals in the $K$-trivial degrees: For $k< n$, let $B_{k/n}$ be the collection of sets that are below any $k$ out of $n$ columns of some random sequence. As before, this is an ideal generated by its c.e.\ elements and the random sequence in the definition can always be taken to be $Ω$. Furthermore, the corresponding cost function characterisation reveals that $B_{k/n}$ is independent of the particular representation of the rational $k/n$, and that $B_p$ is properly contained in $B_q$ for rational numbers $p< q$. These results are proved using a generalisation of the Loomis--Whitney inequality, which bounds the measure of an open set in terms of the measures of its projections. The generality allows us to analyse arbitrary families of orthogonal projections. As it turns out, these do not give us new subideals of the $K$-trivial sets, we can calculate from the family which $B_p$ it characterises. We finish by showing that the the union of $B_p$ for $p<1$ is the collection of sets which are robustly computable from a random, a class previously studied by Hirschfeldt, Jockusch, Kuyper, and Schupp.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Calibrating the complexity of Delta 2 sets via their changes
The computational complexity of a Delta 2 set will be calibrated by the amount of changes needed for any of its computable approximations. Firstly, we study Martin-Loef random sets, where we quantify the changes of initial segments. Secondly, we look at c.e. sets, where we quantify the overall amount of changes by obedience to cost functions. Finally, we combine the two settings. The discussions lead to three basic principles on how complexity and changes relate.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Logic Blog 2012
The 2012 logic blog has focussed on the following: Randomness and computable analysis/ergodic theory; Systematizing algorithmic randomness notions; Traceability; Higher randomness; Calibrating the complexity of equivalence relations from computability theory and algebra.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Characterizing the strongly jump-traceable sets via randomness
We show that if a set $A$ is computable from every superlow 1-random set, then $A$ is strongly jump-traceable. This theorem shows that the computably enumerable (c.e.) strongly jump-traceable sets are exactly the c.e.\ sets computable from every superlow 1-random set. We also prove the analogous result for superhighness: a c.e.\ set is strongly jump-traceable if and only if it is computable from every superhigh 1-random set. Finally, we show that for each cost function $c$ with the limit condition there is a 1-random $Δ^0_2$ set $Y$ such that every c.e.\ set $A \le_T Y$ obeys $c$. To do so, we connect cost function strength and the strength of randomness notions. This result gives a full correspondence between obedience of cost functions and being computable from $Δ^0_2$ 1-random sets.
0 citations0 reviewsNo code linkedOpen access