arXiv preprint ·
A Numerical Refinement of an Exact Discrete Fourier Transform Bound
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We refine the numerical bounds in Kartal's instantiation of Sussman's exact discrete Fourier transform construction. For every integer n >= 1, the resulting algorithm computes the length-n transform with work O(n (log n)^(1 - delta)), where delta = 0.0030201659. The bound holds in an exact complex-arithmetic RAM model with a supplied canonical root of unity. This final exponent saving exceeds the earlier certified parameter C_0 = 0.00302016 by 5.9 x 10^(-9). We retain the underlying circuit, tighten rational bounds for sums of powers of its block and target ranks, and increase the fixed tensor power from 7760 to 11640. These bounds establish the inequalities for Sussman's recursion at the intermediate certificate parameter C = 0.00302016595. The gap C - delta absorbs the overhead of recursion and Fourier reduction. The resulting transform theorem is proved in Lean and checked against the reference problem statement.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Limits and Constants of OpenAI's Claimed ETH Refutation
An $\mathsf{FPRAS}$ for Mixed Volumes
Compressed Oracle Duality: A simple framework for knowing what quantum adversaries know
Quantum Lower Bounds for Collision Problems
Leaving Quantum Bias on the Table: Pushforwards as a Path to Quantum Advantage in Constrained Optimization
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.