Tata Institute of Fundamental Research
Computing on a Full Memory
STCS Seminar
Speaker:
Bruno Loff (Charles University
Department of Computer Science
Malosranske nam. 25, 118 00 Praha 1
Czech Republic)
Organiser:
Arkadev Chattopadhyay
Date:
Wednesday, 20 Apr 2016, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Bruno Loff (Charles University Department of Computer Science Malosranske nam. 25, 118 00 Praha 1 Czech Republic) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Wednesday, 20 Apr 2016, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
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.