[41]

(a) Show that every non-random string x of length n is within Hamming distance O(

√n) of a string y (l(y) = n) such that C(y) > C(x).

(b) Show that this is optimal since the Hamming distance in Item

(a) is

Ω(√n) for some strings.

Comments. Source: [H.M. Buhrman, L. Fortnow, I. Newman, and N.K.

Vereshchagin, Proc. 22nd Symp. Theoret. Aspects Comput. Sci., Lecture Notes Comput. Sci. Vol. 3404, Springer-Verlag, 2005, pp. 412–421]. Hint:

use L.H. Harper’s theorem concerning the expanding properties of the Boolean cube.