On the I/O Complexity of the CYK Algorithm and of a Family of Related DP Algorithms

Lorenzo De Stefani, Vedant Gupta

Asymptotically tight lower bounds are derived for the Input/Output (I/O) complexity of a class of dynamic programming algorithms including matrix chain multiplication, optimal poly…