Lazy Kronecker Product

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^{\omega (\lceil k\mathrm{/}2\rceil ,\lfloor k\mathrm{/}2\rfloor ,a)-a}$ amortized update time and $n^{\omega (\lceil (k-s)\mathrm{/}2\rceil ,\lfloor (k-s)\mathrm{/}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^{\omega (\lceil k\mathrm{/}2\rceil ,\lfloor k\mathrm{/}2\rfloor ,a)-a-\mathrm{\Omega }(1)}$ amortized update time, and $n^{\omega (\lceil (k-s)\mathrm{/}2\rceil ,\lfloor (k-s)\mathrm{/}2\rfloor ,a)-\mathrm{\Omega }(1)}$ worst case query time.