Lazy Kronecker Product

Abstract

In this paper, we show how to generalize the lazy update regime from dynamic matrix product [Cohen, Lee, Song STOC 2019, JACM 2021] to dynamic kronecker product. We provide an algorithm that uses $n^{\ddot{I}‰(\lceil k/2\rceil ,\lfloor k/2\rfloor ,a)-a}$ amortized update time and $n^{\ddot{I}‰(\lceil (k-s)/2\rceil ,\lfloor (k-s)/2\rfloor ,a)}$ worst case query time for dynamic kronecker product problem. Unless tensor MV conjecture is false, there is no algorithm that can use both $n^{\ddot{I}‰(\lceil k/2\rceil ,\lfloor k/2\rfloor ,a)-a-\hat{I}\text{c◯}(1)}$ amortized update time, and $n^{\ddot{I}‰(\lceil (k-s)/2\rceil ,\lfloor (k-s)/2\rfloor ,a)-\hat{I}\text{c◯}(1)}$ worst case query time.