Faster Walsh-Hadamard and discrete Fourier transforms from matrix non-rigidity

DOI10.1145/3564246.3585188MaRDI QIDQ6499243

Josh Alman, Kevin Rao

Publication date: 8 May 2024

zbMATH Keywords

Fourier transformHadamard transformmatrix rigidity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The trade-off between the additive complexity and the asynchronicity of linear and bilinear algorithms
• On the real complexity of a complex DFT
• A new matrix approach to real FFTs and convolutions of length \(2^k\)
• Generating and Searching Families of FFT Algorithms
• An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model
• Complexity Lower Bounds using Linear Algebra
• Tighter Fourier Transform Lower Bounds
• Optimality of the Fast Fourier transform
• A Modified Split-Radix FFT With Fewer Arithmetic Operations
• Probabilistic rank and matrix rigidity
• Matrix rigidity and the Croot-Lev-Pach lemma
• An Algorithm for the Machine Calculation of Complex Fourier Series
• The Tangent FFT
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
• Fourier and Circulant Matrices are Not Rigid
• Kronecker products, low-depth circuits, and matrix rigidity

This page was built for publication: Faster Walsh-Hadamard and discrete Fourier transforms from matrix non-rigidity