Memory exercises and streaming.

The latest guest column on Olivia Judson's "Wild Side" blog at the NYT is on increasing intelligence: Can we do exercises to increase it ? In the article, they describe a test that when performed repeatedly leads to measurable improvement in IQ:

A common way to measure working memory is called the “n-back” task. Presented with a sequential series of items, the person taking the test has to report when the current item is identical to the item that was presented a certain number (n) of items ago in the series. For example, the test taker might see a sequence of letters like

L K L R K H H N T T N X

presented one at a time. If the test is an easy 1-back task, she should press a button when she sees the second H and the second T. For a 3-back task, the right answers are K and N, since they are identical to items three places before them in the list. Most people find the 3-back condition to be challenging.

Of course, to folks who do streaming, this is easily recognized as a simple subcase of detecting a duplicate item in a stream (that problem allows n to vary over the entire stream), which in turn is a special case of the most frequent element estimation problem.

These are hard problems for sublinear space stream algorithms. It's interesting that they're taxing for human working memory as well.