[43] Let U be a standard machine as in Exercise 7.3.15.

(a) Show that there exists a probabilistic algorithm that on input a string x of length n and a rational number δ satisfying 0 <δ< 1 outputs a list of n strings that with probability at least 1−δ contains a program for x of length C(x) +O(log(n/δ)). This probabilistic program uses O(log(n/δ))

random bits and can be executed in space 2O(n) + 1/δ.

(b) Show that there exists a probabilistic algorithm that on input a string x of length n and a rational number δ satisfying 0 <δ< 1 outputs in polynomial time in (n and 1/δ) a list of n strings that with probability at least 1 − δ contains a program for x of length C(x) + O(log2(n/δ)).

This probabilistic program uses O(log2(n/δ)) random bits.

Comments. Source: [B. Bauwens and M. Zimand, Proc. 29th IEEE Conf.
Comput. Complexity, 2014, 241–247]. Hint for Items

(a) and (b): use standard machines defined in Exercise  7.3.15.

Construct a bipartite graph which is an extractor with the ‘rich owner’ property, which means roughly the following. No matter how we restrict the left side to a subset of a certain size, in the restricted graph most left nodes ‘own’ most of their neighbors in the sense that these neighbors are not shared with any other node.