Suggestions - Jan 18 2024

Reading topics

Recent interesting articles

Optimal bounds for single-source Kolmogorov extractors

Nice paper exploring exact randomness extraction bounds using combinatorial methods (hypergraphs).

Intermediate intrinsic density and randomness

Assymptotic density is a popular topic today in computability. Here he considers density which is invariant under computable permutations, which he calls intrinsic. Interesting work.

Left c.e. reals alpha and C(alpha)

Nice short paper around a lemma of Frank Stephan. Essential if you are interested in the Kolmogorov complexity of left c.e. reals.

The Frequent Paucity of Trivial Strings

Good note around Chaitin’s characterization of computability. Read.

Partial functions and domination

Domination is important in computability. Domination with partial functions is what they look at here.

Information decomposition diagrams applied beyond shannon entropy

Looks interesting.

Suggested Open problems

Suggestion 1. In this paper they show that in the Solovay degrees of left c.e. reals, Schnorr randomness is not upward closed. Question: are the left c.e. Schnorr random reals are upward dense: is it true that for every left c.e. real x there exists left c.e. and non-random but Schnorr random real y which is Solovay above x ?

Hint. I suggested a positive answer through a modification of the proof of Theorem 8.11.1 in the book of Downey/Hirschfeldt. In emails with Nies (one of the authors of the above theorem) I say “Right now it seems to me that one can modify the proof of Nies-Stephan-Terwijn (making Schnorr lce in every high c.e degree) to show upward density. Given lce solovay incomplete beta, one would wtt-code beta (along with a function dominating all computable functions) into a left c.e. α so that α + β is Schnorr but not ML-random. It seems to me that the wtt-coding of beta into alpha would suffice for alpha to make decisions about keeping the partial martingale M bounded on α + β.”

Difficulty Medium. You need to understand the proof of the Nies-Stephan-Terwijn theorem (Theorem 8.11.1 in Downey/Hirschfeldt). Nies finds this plausible so, you can try if it works.

Suggestion 2. In Lemma 8 of [Speedable Left-c.e. Numbers by Titov and Merkle] they show that if a left-c.e. real is speedable then it is ρ-speedable for any ρ > 0.

Project. In emails I suggested that this method can be combined with finite injury to show that every speedable left-c.e. real is 0-speedable. The group in Heidelberg was able to show this for c.e. sets, but not for left-c.e. reals. You can try to follow my suggestion, or show that I’m wrong.

Difficulty. seems doable.

Research Question Forums

Reading science blogs and forums can be beneficial.

You can also ask your own questions and see research ideas at an early stage.

Many of these are frequented by top researchers.

About Compression

It is good to be in touch with both practical and theoretical aspects of compression.

Food for thought