Computing on a Full Memory

Arkadev Chattopadhyay
Wednesday, 20 Apr 2016, 16:00 to 17:00
A-201 (STCS Seminar Room)
Abstract: Suppose that you have log(n) bits of free working memory, plus an additional poly(n) bits of auxiliary memory which is *full*. Meaning, the auxiliary memory has some contents, and you are allowed to read/write into it, but you must promise that by the time your computation is done, the contents of the auxiliary memory have been restored to their original state.

While it may appear at first that the full memory is useless, it turns out that you can make a non-trivial use of it to boost the power of your computation.

I will show that directed connectivity can be computed in this way (with log(n) working space and poly(n) full memory), and related results around this problem.