Please note: This seminar will take place in DC 1304 and online.
Roei Tell, Assistant Professor
Department of Computer and Mathematical Sciences, University of Toronto
Given two algorithms $A_1$ and $A_2$ each using low space, what is the complexity of computing the composed function $A_2( A_1(x) )$? The two known approaches for composition are expensive either in time or in space, and interpolating them yields a quadratic time-space curve. This work asks whether quadratic time-space is optimal.
We prove an unconditional lower bound for composing linear-time algorithms, and then show that proving the same lower bound in various other natural settings (e.g., for algorithms running in large polynomial time) would imply a breakthrough on a major open problem in complexity theory, namely the BPL = L problem. The main contribution in the work is connecting three questions: the complexity of composition, time-space tradeoffs for deterministic algorithms, and BPL = L.
Based on an upcoming work with Ted Pyne, and the lower bound proof uses an idea of Ryan Williams.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.