[35] For every polynomial p and sufficiently large n, there exists a set of strings A ⊆ {0, 1}∗ such that A=n contains more than 2n/50 strings and there is an x ∈ A=n with CDp(x|A=n) ≥ 2 log d(A=n) − O(1).

Comments. This and Exercise 7.2.4 answer the open question posed in Exercise 7.2.3 in the second edition of this book. Source: [H. Buhrman, S.

Laplante, and P. Miltersen, Proc. 15th IEEE Conf. Comput. Complexity, 2000, pp. 126–130].