Faster Walsh-Hadamard and discrete Fourier transforms from matrix non-rigidity
From MaRDI portal
Publication:6499243
DOI10.1145/3564246.3585188MaRDI QIDQ6499243FDOQ6499243
Authors: Josh Alman, Kevin Rao 
Publication date: 8 May 2024
Cites Work
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Title not available (Why is that?)
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
- Complexity Lower Bounds using Linear Algebra
- A Modified Split-Radix FFT With Fewer Arithmetic Operations
- A new matrix approach to real FFTs and convolutions of length \(2^k\)
- A lower bound for Fourier transform computation in a linear model over \(2\times 2\) unitary gates using matrix entropy
- The trade-off between the additive complexity and the asynchronicity of linear and bilinear algorithms
- On the real complexity of a complex DFT
- Generating and searching families of FFT algorithms
- Optimality of the Fast Fourier transform
- Probabilistic rank and matrix rigidity
- Matrix rigidity and the Croot-Lev-Pach lemma
- Fourier and circulant matrices are not rigid
- Title not available (Why is that?)
- An \(\mathrm{Omega}((n \log n)/R)\) lower bound for Fourier transform computation in the \(R\)-well conditioned model
- Tighter Fourier transform lower bounds
- Kronecker products, low-depth circuits, and matrix rigidity
- The Tangent FFT
This page was built for publication: Faster Walsh-Hadamard and discrete Fourier transforms from matrix non-rigidity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499243)
