Complexity Explorer Santa Few Institute

1. Which of these could function as a coarse-graining prescription?

A. mapping red to blue, and blue to red, in an RGB color image

B. anonymizing sensitive health data from a hospital, so that each person is represented by a unique ID, but individual's privacy is protected by the ID does not tell you the person's real name

C. listing the frequencies of all the words in Tolstoy's War and Peace

D. translating a book from English to German.

 

Answer: (C): by considering only word frequencies, we throw out an enormous amount of the content of War and Peace, including all the structure contained in the word order. (A) transforms an image, but does not reduce the amount of information in it -- we can, for example, still recover the original image by mapping blue back to red, and red to blue. Similarly, although (B) is an irreversible mapping (once you throw away the key), it still preserves the full complexity of the data. (D) is perhaps a trickier case; under the assumption that the translator is good, and that German is equally expressive as English, the translation is not reduced in complexity or complicatedness; the text may be transformed, and even come to have a different meaning for a reader, but should not be significantly simplified compared to the original.

 

2. What needs to be true for the JPEG algorithm to count as a coarse-graining?​

A. it reduces the file size: the output of the JPEG algorithm is smaller than the original bitmap image file.

B. it is irreversible: given a JPEG compression, I can't recover the original image.

C. it doesn't look the same as the original image.

D. (A) and (B), but not (C)

 

Answer: (D). (A) alone is not enough, because it may be possible to compress the image without destroying information (in the same way we make a zip file in Mac OS X, compressing files without loss). (B) alone is not enough because an encryption algorithm (once the key is lost) will be irreversible, but not a simplification. (C) turns out to be neither necessary nor sufficient; it's not sufficient to indicate I've done a coarse graining, because I could get a different image by just inverting all the pixels, or rotating it ninety degrees, but neither of these amount to a simplification. Nor is it necessary: I might have done a coarse-graining that's invisible to the eye. Just because something looks the same to my visual system doesn't mean that no coarse-graining happened -- I may just not be able to perceive the difference because my visual system itself is performing a coarse-graining before sending the signals back to my conscious awareness.