[Theory] UC Theory Seminar

[Alexander Razborov via Theory]

 Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar

Thursday, November 7, 3:30pm
Location: Kent 102

SPEAKER: Josh Alman (Columbia University)

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