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.

**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.

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.

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

- How PNG Works: Compromising Speed for Quality
- Huffman Codes: An Information Theory Perspective
- Stanford Seminar - Information Theory of Deep Learning, Naftali Tishby
- The Unreasonable Effectiveness of JPEG: A Signal Processing Approach
- How are memories stored in neural networks?