BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1761
DTSTAMP:20260813T043257Z
SUMMARY:Even a Bad Matrix Multiplier is Good Enough\, if You Correct It
DESCRIPTION:Speaker: Soham Chatterjee (TIFR)\n\nAbstract: \nImagine a devic
 e that multiplies two matrices very fast\, but unreliably: only a small co
 nstant fraction of the entries in its output are correct\, and even this i
 s guaranteed only when the input matrices are random. On the matrices you 
 actually care about\, it may behave arbitrarily badly. Can such a device s
 till be useful? \nIn this talk\, we will see a recent result of Hirahara 
 and Shimizu (STOC 2025) showing that the answer is yes\, in the strongest 
 possible sense: any such device can be converted into a fast randomized al
 gorithm that computes matrix multiplication exactly\, on all inputs. Over 
 a finite field with $p$ elements\, one can always get a $1/p$ fraction of 
 entries right by blind guessing\; the result shows that any algorithm doin
 g even slightly better than this trivial baseline can be fully error-corre
 cted\, so the threshold is optimal. This is what is called a "worst-case e
 xact to average-case approximate" reduction\, and it resolves a question l
 eft open by earlier work on the average-case complexity of matrix multipli
 cation. \n \nA central idea in the proof comes from the theory of error-
 correcting codes. Instead of feeding the matrices $A$ and $B$ to the unrel
 iable device directly\, we first encode them: applying a linear code with 
 encoding matrix $Q$\, we hand the device the matrices $QA$ and $(QB^{\\per
 p})^{\\perp}$. The point is that the product of these encoded matrices equ
 als $QABQ^{\\perp}$\, which is precisely the answer $AB$ encoded from the 
 left and the right. The device's noisy output is therefore a corrupted cod
 eword of this two-sided encoding\, and if the underlying code is a good li
 st-decodable\, such as the Reed-Solomon code\, we can decode it column by 
 column and then row by row to recover a short list of candidates containin
 g $AB$\, from which the true product is identified by a fast randomized ve
 rification. The talk will be self-contained and should be accessible to an
 yone comfortable with basic linear algebra and probability.\n \nRefernce:
  We follow the paper "Error Correction of Matrix Multiplication Algorithms
 " by Shichi Hirahara and Nobutaka Shimizu (STOC 2025). Link: https://eccc
 .weizmann.ac.il/report/2025/031/\n
URL:https://www.tcs.tifr.res.in/web/events/1761
DTSTART;TZID=Asia/Kolkata:20260814T160000
DTEND;TZID=Asia/Kolkata:20260814T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR