[Colloquium] U of C - CS Theory Seminar - November 19, 2024

[Jose J Fragoso via Colloquium]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS



Josh Alman
Columbia University

 [cid:image001.png at 01DB35AC.BD8CF420]

Tuesday, November 19, 2024 at 3:30pm
Kent Chemical Laboratory, Room 102


Title: Faster Walsh-Hadamard Transform from Matrix Non-Rigidity

Abstract: 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:

- 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.

- 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.

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.

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.


Bio: Josh Alman is an Assistant Professor of Computer Science at Columbia University. He works in algorithm design and complexity theory, and particularly focuses on developing and applying algebraic tools like fast matrix multiplication, Fourier transforms, and polynomial approximations. His recent awards include a David & Lucile Packard Fellowship, an NSF CAREER award, and a Google Research Scholar Award.






Host: Alexander Razborov








-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20241113/80acd8e3/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 1107642 bytes
Desc: image001.png
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20241113/80acd8e3/attachment-0001.png>