<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div dir="ltr"><meta http-equiv="content-type" content="text/html; charset=utf-8"><div dir="ltr"><b style="font-family: Calibri, sans-serif; font-size: 10pt; -webkit-text-size-adjust: auto;"><span style="font-size: 14pt; font-family: Helvetica;"> Josh Alman</span></b><meta http-equiv="content-type" content="text/html; charset=utf-8"><div dir="ltr"></div></div><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 14pt;">Columbia University<o:p></o:p></span></b></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> <img alt="image001.png" src="cid:E08D2AFA-94B9-46DD-B5CD-F2F42BC89E2F"></span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><o:p> </o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt;"><span dir="ltr">Tuesday, </span></span></b><b><span style="font-size: 11pt;"><span dir="ltr">November 19</span><span dir="ltr">, 202</span><span dir="ltr">4</span><span dir="ltr"> at 3:30pm</span></span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; background: yellow;">Kent Chemical Laboratory, Room 102</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><i><span style="font-size: 12pt;">Title</span></i></b><span style="font-size: 12pt;">: Faster Walsh-Hadamard Transform from Matrix Non-Rigidity<br><br><b><i>Abstract:</i></b> The Walsh-Hadamard transform is a simple recursively-defined linear transformation with many applications throughout algorithm design and complexity theory. The folklore "fast Walsh-Hadamard transform" algorithm computes it using only N log N arithmetic operations, which is believed to be optimal up to constant factors. In this talk, I'll give two improved constructions:<br><br>- A new algorithm which uses (23/24) N log N + O(N) arithmetic operations. This is, to my knowledge, the first improvement on the leading constant.<br><br>- A new depth-2 linear circuit of size O(N^{1.45}), improving on size O(N^{1.5}) which one gets from the fast Walsh-Hadamard transform approach.<br><br>A key idea behind both constructions is to take advantage of the matrix non-rigidity of the Walsh-Hadamard transform. A matrix is called "rigid" if it's impossible to change a "small" number of its entries to make it have "low" rank. L. Valiant showed that if a matrix is rigid, then this implies lower bounds for computing its linear transformation. However, a recent line of work has shown that many matrices of interest, including the Walsh-Hadamard transform, are actually not rigid. Although a formal converse to Valiant's result is not known, we'll make use of non-rigidity in our new constructions.<br><br>Based mostly on joint work with Yunfeng Guan, Ashwin Padaki, and Kevin Rao, but I'll also discuss very recent progress with Jingxun Liang and Baitian Li.</span></p></div></body></html>