Buchumschlag

Did Fourier Really Meet Möbius? Fast Subset Convolution via FFT

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Stoian, Mihail
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Approximate Min-Sum Subset Convolution
von: Stoian, Mihail
Veröffentlicht: (2024)

Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More
von: Stoian, Mihail
Veröffentlicht: (2026)

TSP Escapes the $O(2^n n^2)$ Curse
von: Stoian, Mihail
Veröffentlicht: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
von: Stoian, Mihail
Veröffentlicht: (2024)

On the Optimal Linear Contraction Order of Tree Tensor Networks, and Beyond
von: Stoian, Mihail, et al.
Veröffentlicht: (2022)

Fast Compressed-Domain N-Point Discrete Fourier Transform: The "Twiddless" FFT Algorithm
von: Queiroz, Saulo
Veröffentlicht: (2025)

Permutation-Avoiding FFT-Based Convolution
von: Venkovic, Nicolas, et al.
Veröffentlicht: (2025)

Subset Balancing and Generalized Subset Sum via Lattices
von: Gao, Yiming, et al.
Veröffentlicht: (2026)

Interval Selection in Sliding Windows
von: Alexandru, Cezar-Mihail, et al.
Veröffentlicht: (2024)

Beating Bellman's Algorithm for Subset Sum
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

Learning Dependency Models for Subset Repair
von: Li, Haoda, et al.
Veröffentlicht: (2025)

Derandomizing Pseudopolynomial Algorithms for Subset Sum
von: Chan, Timothy M.
Veröffentlicht: (2026)

An Improved Pseudopolynomial Time Algorithm for Subset Sum
von: Chen, Lin, et al.
Veröffentlicht: (2024)

Inverse Quadratic Decay in Random Subset Sum
von: Chen, Edwin, et al.
Veröffentlicht: (2026)

Sumsets, 3SUM, Subset Sum: Now for Real!
von: Fischer, Nick
Veröffentlicht: (2024)

Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance
von: Song, Zhao, et al.
Veröffentlicht: (2022)

Online Rounding for Set Cover under Subset Arrivals
von: Byrka, Jarosław, et al.
Veröffentlicht: (2025)

An Almost Quadratic Vertex Kernel for Subset Feedback Arc Set in Tournaments
von: Bai, Tian
Veröffentlicht: (2025)

Optimal Dynamic Parameterized Subset Sampling
von: Gan, Junhao, et al.
Veröffentlicht: (2024)

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
von: Aggarwal, Divesh, et al.
Veröffentlicht: (2024)

Breaking the Barrier $2^k$ for Subset Feedback Vertex Set in Chordal Graphs
von: Bai, Tian, et al.
Veröffentlicht: (2022)

Subset-lex: did we miss an order?
von: Arndt, Jörg
Veröffentlicht: (2014)

Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2020)

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
von: Alman, Josh, et al.
Veröffentlicht: (2025)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
von: Anand, Aditya, et al.
Veröffentlicht: (2025)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

Beating Meet-in-the-Middle for Subset Balancing Problems
von: Randolph, Tim, et al.
Veröffentlicht: (2025)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
von: Jin, Ce, et al.
Veröffentlicht: (2024)

Clustering with Non-adaptive Subset Queries
von: Black, Hadley, et al.
Veröffentlicht: (2024)

Improved Space Bounds for Subset Sum
von: Belova, Tatiana, et al.
Veröffentlicht: (2024)

Fast exact algorithms via the Matrix Tree Theorem
von: Arvind, V., et al.
Veröffentlicht: (2025)

Designing Compact ILPs via Fast Witness Verification
von: Włodarczyk, Michał
Veröffentlicht: (2025)

Convolution and Knapsack in Higher Dimensions
von: Grage, Kilian, et al.
Veröffentlicht: (2024)

Unit Interval Selection in Random Order Streams
von: Alexandru, Cezar-Mihail, et al.
Veröffentlicht: (2026)

Distribution Testing Meets Sum Estimation
von: Pradhan, Pinki, et al.
Veröffentlicht: (2025)

Does Subset Sum Admit Short Proofs?
von: Włodarczyk, Michał
Veröffentlicht: (2024)

Subset verification and search algorithms for causal DAGs
von: Choo, Davin, et al.
Veröffentlicht: (2023)

Deterministic Monotone Min-Plus Product and Convolution
von: Jin, Ce, et al.
Veröffentlicht: (2026)

Hitting Meets Packing: How Hard Can it Be?
von: Focke, Jacob, et al.
Veröffentlicht: (2024)

Fair Correlation Clustering Meets Graph Parameters
von: Blaha, Johannes, et al.
Veröffentlicht: (2026)