Theory Seminar, Wednesday Nov 13: Dean Doron (BGU) - Approximating Iterated Multiplication of Stochastic Matrices in Small Space
3 views
Skip to first unread message
Arnold Filtser
Nov 7, 2024, 2:37:32 AM11/7/24
to BIU Theory Seminar, de...@bgu.ac.il
Hi all,
Speaker: Dean Doron (BGU)
Title: Approximating Iterated Multiplication of Stochastic Matrices in Small Space
Abstract: Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem’s space complexity, as it constitutes the main route towards resolving the BPL vs. L problem.
In this talk, we give the first polynomial improvement over the seminal work by Saks and Zhou (1999), who gave a deterministic algorithm for approximating the product of n stochastic matrices of dimension w×w in space O(log3/2n+ (log n)1/2·log w). Our algorithm achieves space complexity of O~(log n+ (log n)1/2·log w), which outperforms [SZ99] whenever n >> w. In particular, in the regime log n > log2w, our algorithm runs in nearly-optimal O~(log n) space, improving upon the previous best O(log3/2n).
Time permitting, I will also survey other recent advances and challenges in derandomization space-bounded algorithms.
Joint work with Gil Cohen, Ori Sberlo, and Amnon Ta-Shma
Next week (Wed Nov 13, at 12:00) we will meet for our theory seminar.
Location: Building 503 room 226.
See you all there,
Title: Approximating Iterated Multiplication of Stochastic Matrices in Small Space
Abstract: Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem’s space complexity, as it constitutes the main route towards resolving the BPL vs. L problem.
In this talk, we give the first polynomial improvement over the seminal work by Saks and Zhou (1999), who gave a deterministic algorithm for approximating the product of n stochastic matrices of dimension w×w in space O(log3/2n+ (log n)1/2·log w). Our algorithm achieves space complexity of O~(log n+ (log n)1/2·log w), which outperforms [SZ99] whenever n >> w. In particular, in the regime log n > log2w, our algorithm runs in nearly-optimal O~(log n) space, improving upon the previous best O(log3/2n).
Time permitting, I will also survey other recent advances and challenges in derandomization space-bounded algorithms.
Joint work with Gil Cohen, Ori Sberlo, and Amnon Ta-Shma
Arnold Filtser
Nov 13, 2024, 4:01:00 AM11/13/24
to BIU Theory Seminar, de...@bgu.ac.il
The seminar starts in one hour!
Reply all
Reply to author
Forward
0 new messages