@article{cooleyTukey1965,
  author = {Cooley, James W. and Tukey, John W.},
  title = {An Algorithm for the Machine Calculation of Complex {Fourier} Series},
  journal = {Mathematics of Computation},
  volume = {19},
  number = {90},
  pages = {297--301},
  year = {1965},
  month = apr,
  doi = {10.1090/S0025-5718-1965-0178586-1},
  url = {https://doi.org/10.1090/S0025-5718-1965-0178586-1}
}

@article{morgenstern1973,
  author = {Morgenstern, Jacques},
  title = {Note on a Lower Bound on the Linear Complexity of the Fast {Fourier} Transform},
  journal = {Journal of the ACM},
  volume = {20},
  number = {2},
  pages = {305--306},
  year = {1973},
  month = apr,
  doi = {10.1145/321752.321761},
  url = {https://doi.org/10.1145/321752.321761}
}

@misc{ailon2013,
  author = {Ailon, Nir},
  title = {A Lower Bound for {Fourier} Transform Computation in a Linear Model Over {$2\times2$} Unitary Gates Using Matrix Entropy},
  year = {2013},
  howpublished = {arXiv:1305.4745v1},
  note = {Version of 21 May 2013},
  doi = {10.48550/arXiv.1305.4745},
  url = {https://arxiv.org/abs/1305.4745v1}
}

@misc{ailon2014,
  author = {Ailon, Nir},
  title = {An {$\Omega((n\log n)/R)$} Lower Bound for {Fourier} Transform Computation in the {$R$}-Well Conditioned Model},
  year = {2014},
  howpublished = {arXiv:1403.1307v5},
  note = {Version of 24 July 2014},
  doi = {10.48550/arXiv.1403.1307},
  url = {https://arxiv.org/abs/1403.1307v5}
}

@inproceedings{almanRao2023,
  author = {Alman, Josh and Rao, Kevin},
  title = {Faster {Walsh--Hadamard} and Discrete {Fourier} Transforms from Matrix Non-rigidity},
  booktitle = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing},
  series = {STOC 2023},
  pages = {455--462},
  publisher = {Association for Computing Machinery},
  year = {2023},
  doi = {10.1145/3564246.3585188},
  url = {https://arxiv.org/abs/2211.06459v2},
  note = {Full version: arXiv:2211.06459v2, 14 June 2023}
}

@book{boydVandenberghe2004,
  author = {Boyd, Stephen and Vandenberghe, Lieven},
  title = {Convex Optimization},
  publisher = {Cambridge University Press},
  year = {2004},
  isbn = {978-0-521-83378-3},
  url = {https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf}
}

@misc{almanLi2025,
  author = {Alman, Josh and Li, Baitian},
  title = {Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum},
  year = {2025},
  howpublished = {arXiv:2509.14489v1},
  note = {Version of 17 September 2025},
  doi = {10.48550/arXiv.2509.14489},
  url = {https://arxiv.org/abs/2509.14489v1}
}

@misc{stacksProject,
  author = {{The Stacks Project Authors}},
  title = {The {Stacks Project}},
  year = {2026},
  url = {https://stacks.math.columbia.edu},
  note = {Tags 02JJ, 00GQ, and 08ZU; accessed 25 September 2026}
}

@article{kailathKungMorf1979,
  author = {Kailath, Thomas and Kung, Sun-Yuan and Morf, Martin},
  title = {Displacement ranks of a matrix},
  journal = {Bulletin of the American Mathematical Society (New Series)},
  volume = {1},
  number = {5},
  pages = {769--773},
  year = {1979},
  doi = {10.1090/S0273-0979-1979-14659-7},
  url = {https://doi.org/10.1090/S0273-0979-1979-14659-7}
}

@article{orucPhillips2000,
  author = {Oru{\c{c}}, Halil and Phillips, George M.},
  title = {Explicit Factorization of the {Vandermonde} Matrix},
  journal = {Linear Algebra and its Applications},
  volume = {315},
  number = {1--3},
  pages = {113--123},
  year = {2000},
  doi = {10.1016/S0024-3795(00)00124-5},
  url = {https://doi.org/10.1016/S0024-3795(00)00124-5}
}

@article{kuznetsov2018,
  author = {Kuznetsov, Alexey},
  title = {Using {$q$}-Calculus to Study {$LDL^{\mathsf T}$} Factorization
           of a Certain {Vandermonde} Matrix},
  journal = {Operators and Matrices},
  volume = {12},
  number = {3},
  pages = {773--777},
  year = {2018},
  doi = {10.7153/oam-2018-12-45},
  url = {https://files.ele-math.com/articles/oam-12-45.pdf}
}

@article{good1958,
  author = {Good, I. J.},
  title = {The interaction algorithm and practical {Fourier} analysis},
  journal = {Journal of the Royal Statistical Society, Series B (Methodological)},
  volume = {20},
  number = {2},
  pages = {361--372},
  year = {1958},
  doi = {10.1111/j.2517-6161.1958.tb00300.x},
  url = {https://doi.org/10.1111/j.2517-6161.1958.tb00300.x}
}

@article{cooleyLewisWelch1967,
  author = {Cooley, James W. and Lewis, Peter A. W. and Welch, Peter D.},
  title = {Historical notes on the fast {Fourier} transform},
  journal = {Proceedings of the IEEE},
  volume = {55},
  number = {10},
  pages = {1675--1677},
  year = {1967},
  doi = {10.1109/PROC.1967.5959},
  url = {https://doi.org/10.1109/PROC.1967.5959}
}


@article{bennett1973,
  author = {Bennett, Charles H.},
  title = {Logical Reversibility of Computation},
  journal = {IBM Journal of Research and Development},
  volume = {17}, number = {6}, pages = {525--532}, year = {1973},
  doi = {10.1147/rd.176.0525},
  url = {https://doi.org/10.1147/rd.176.0525}
}

@inproceedings{buhrmanEtAl2014,
  author = {Buhrman, Harry and Cleve, Richard and Kouck{\'y}, Michal
            and Loff, Bruno and Speelman, Florian},
  title = {Computing with a Full Memory: Catalytic Space},
  booktitle = {Proceedings of the Forty-Sixth Annual ACM Symposium
               on Theory of Computing},
  series = {STOC '14}, publisher = {Association for Computing Machinery},
  year = {2014}, pages = {857--866},
  doi = {10.1145/2591796.2591874},
  url = {https://doi.org/10.1145/2591796.2591874}
}

@article{seeleyRichardLove2012,
  author = {Seeley, Jacob T. and Richard, Martin J. and Love, Peter J.},
  title = {The {Bravyi--Kitaev} Transformation for Quantum Computation
           of Electronic Structure},
  journal = {The Journal of Chemical Physics},
  volume = {137}, pages = {224109}, year = {2012},
  doi = {10.1063/1.4768229},
  url = {https://doi.org/10.1063/1.4768229}
}

@article{bluestein1970,
  author = {Bluestein, Leo I.},
  title = {A Linear Filtering Approach to the Computation of
           Discrete {Fourier} Transform},
  journal = {IEEE Transactions on Audio and Electroacoustics},
  volume = {18}, number = {4}, pages = {451--455}, year = {1970},
  doi = {10.1109/TAU.1970.1162132},
  url = {https://doi.org/10.1109/TAU.1970.1162132}
}

@article{rabinerSchaferRader1969,
  author = {Rabiner, Lawrence R. and Schafer, Ronald W. and Rader, Charles M.},
  title = {The Chirp $z$-Transform Algorithm},
  journal = {IEEE Transactions on Audio and Electroacoustics},
  volume = {17}, number = {2}, pages = {86--92}, year = {1969},
  doi = {10.1109/TAU.1969.1162034},
  url = {https://doi.org/10.1109/TAU.1969.1162034}
}

@misc{openaiExplicitFourier2026,
  author = {{OpenAI}},
  title = {{An explicit power saving for the exact discrete Fourier transform}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/An-explicit-power-saving-for-the-exact-discrete-Fourier-transform-September-25-2026/main.pdf}{OAI:An-explicit-power-saving-for-the-exact-discrete-Fourier-transform-September-25-2026}},
  year = {2026}
}