Please note: This seminar will take place in DC 2568.
Edward Pyne, PhD student
Department of Electrical Engineering and Computer Science, MIT
When complexity theorists (like me!) talk about computing functions in small space, we picture a read-only input, a small worktape, and a write-only output. When practitioners think about computing functions in small space, they think of an input x that must be transformed into an output f(x), using few additional bits. Because this model is arguably less clean, it previously escaped the attention of complexity theorists
We show that complexity can play a useful role in understanding “in-place space-bounded computation”. For instance, assuming cryptography exists, it is impossible to transform (x,y) to x*y in-place. We give a variety of algorithms and lower bounds for the model, and use these to prove new results in catalytic computing. I will also discuss open problems and directions.
Joint work with James Cook, Surendra Ghentiyala, Ian Mertz, and Nathan Sheffield.