Department of Computer Science
Malosranske nam. 25, 118 00 Praha 1
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.