Cover Image

Safety-Certified CRT Sparse FFT: $Ω(k^2)$ Lower Bound and $O(N \log N)$ Worst-Case

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Flouro, Aaron R., Chadwick, Shawn P.
Format:	Preprint
Published:	2026
Subjects:	Signal Processing Data Structures and Algorithms Information Theory 65T50, 68Q25 F.2.1; G.1.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Deterministic Sparse FFT via Keyed Multi-View Gating with $O(\sqrt{N} \log k)$ Expected Time
by: Flouro, Aaron R., et al.
Published: (2026)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

Hallucinations Live in Variance
by: Flouro, Aaron R., et al.
Published: (2026)

Sparse Knowledge Distillation: A Mathematical Framework for Probability-Domain Temperature Scaling and Multi-Stage Compression
by: Flouro, Aaron R., et al.
Published: (2026)

Experimental algorithms for the dualization problem
by: Mezzini, Mauro, et al.
Published: (2025)

Complete Decomposition of Symmetric Tensors in Linear Time and Polylogarithmic Precision
by: Koiran, Pascal, et al.
Published: (2022)

Quantum Search without Global Diffusion
by: Burke, John, et al.
Published: (2026)

On (In)approximability of MaxMin Independent Set Reconfiguration
by: Hoang, Hung P., et al.
Published: (2026)

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
by: Heimann, Sophia, et al.
Published: (2026)

Multi-variable Quantification of BDDs in External Memory using Nested Sweeping (Extended Paper)
by: Sølvsten, Steffan Christ, et al.
Published: (2024)

The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
by: Heimann, Sophia, et al.
Published: (2024)

Space-Time Trade-off in Integer Linear Scaling Rounded to the Nearest Integer through Multiplicative and Additive Decomposition
by: Kim, Kyeong Soo
Published: (2026)

Tensor Decomposition for Non-Clifford Gate Minimization
by: Khoruzhii, Kirill, et al.
Published: (2026)

Efficient Binary Decision Diagram Manipulation in External Memory
by: Sølvsten, Steffan Christ, et al.
Published: (2021)

$XX^{t}$ Can Be Faster
by: Rybin, Dmitry, et al.
Published: (2025)

Modern column generation for estimating single- and multi-purchase ranked list choice models
by: Costa, Luciano, et al.
Published: (2026)

On the twin-width of near-regular graphs
by: Heinrich, Irene, et al.
Published: (2025)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
by: Heimann, Sophia, et al.
Published: (2025)

Overlapping Biclustering
by: Bentert, Matthias, et al.
Published: (2025)

Simple minimally unsatisfiable subsets of 2-CNFs
by: Kullmann, Oliver, et al.
Published: (2026)

On the Average Runtime of an Open Source Binomial Random Variate Generation Algorithm
by: Cicirello, Vincent A.
Published: (2024)

Matrix-by-matrix multiplication algorithm with $O(N^2log_2N)$ computational complexity for variable precision arithmetic
by: Paszyński, Maciej
Published: (2024)

An Explicit and Efficient $O(n^2)$-Time Algorithm for Sorting Sumsets
by: Mundhra, S.
Published: (2025)

Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
by: Feldman, Moran, et al.
Published: (2026)

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
by: Bonnet, Édouard, et al.
Published: (2026)

Faster Algorithms for Structured Matrix Multiplication via Flip Graph Search
by: Khoruzhii, Kirill, et al.
Published: (2025)

Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
by: Bojikian, Narek, et al.
Published: (2025)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
by: Li, Zhangsong
Published: (2026)

A Polynomial-Time Deterministic Algorithm for an NP-Complete Problem
by: Jiang, Xinwen, et al.
Published: (2021)

Predicting Memory Demands of BDD Operations using Maximum Graph Cuts (Extended Paper)
by: Sølvsten, Steffan Christ, et al.
Published: (2023)

Symbolic Model Checking in External Memory
by: Sølvsten, Steffan Christ, et al.
Published: (2025)

A Simple and Efficient Algorithm for Sorting Signed Permutations by Reversals
by: Swenson, Krister M.
Published: (2024)

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences
by: Kosoy, Vanessa
Published: (2026)

Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
by: Buchbinder, Niv, et al.
Published: (2024)

Explicit Bounds and Parallel Algorithms for Counting Multiply Gleeful Numbers
by: Moore, Sara, et al.
Published: (2025)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
by: Grochow, Joshua A., et al.
Published: (2021)

Count-Free Weisfeiler--Leman and Group Isomorphism
by: Collins, Nathaniel A., et al.
Published: (2022)