[Theory] UC Theory seminar: a reminder

[Alexander Razborov via Theory]

Josh Alman
Columbia University
 
 
 
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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241118/8ea084f4/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 457024 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20241118/8ea084f4/attachment-0001.png>