Seminars
View all Seminars | Download ICal for this eventMatrix Multiplication And Verification Using Coding Theory
Series: Bangalore Theory Seminars
Speaker: Karthik Gajulapalli
Date/Time: Feb 04 16:00:00
Location: CSA Auditorium, (Room No. 104, Ground Floor)
Abstract:
We study the Matrix Multiplication Verification Problem (MMV) where the goal is, given three n ? n matrices A, B, and C as input, to decide whether AB = C. A classic randomized algorithm by Freivalds (MFCS, 1979) solves MMV in O(n^2) time, and a longstanding challenge is to (partially) derandomize it while still running in faster than matrix multiplication time (i.e., in o(n^?) time).
To that end, we give two algorithms for MMV in the case where AB - C is *sparse*. Specifically, when AB - C has at most O(n^δ) non-zero entries for a constant 0 <= δ < 2, we give (1) a deterministic O(n^{???ε})-time algorithm for constant ε = ε(δ) > 0, and (2) a randomized O(n^2)-time algorithm using (δ/2) * log(n) + O(1) random bits.
We then lift our ideas from the Verification to Multiplication. If the product AB of the two matrices is promised to be sparse, then we give a deterministic algorithm that computes the product in o(n^?) time.
Our algorithms are simple and use techniques from coding theory.
Joint work with Huck Bennett, Alexander Golovnev, and Evelyn Warton.
Microsoft teams:
Link
We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series
Hosts: KVN Sreenivas, Rameesh Paul, Rahul Madhavan, Debajyoti Kar