Reproduce “A Numerical Refinement of an Exact Discrete Fourier Transform Bound” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Zhihao Yao, Sichao Liu
The authors prove that a fixed deterministic algorithm computes every length-n discrete Fourier transform in O(n(log n)^(1−δ)) work, with δ=0.0030201659, using exact complex arithmetic and a supplied canonical root of unity. They retain Kartal’s circuit and reduction, tightening rational rank-moment estimates and increasing the tensor power. This is an all-length asymptotic result, not a practical speedup.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.