2008/01/31 by Amihood Amir, Klim Efremenko, Amir, Amihood +7 · 1 citation
Computer Science · Mathematics · #Advanced Data Compression Techniques #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Computer science #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Geometry #Mathematics #Reduction (mathematics) #cs.DS
paper · pdf · doi:10.48550/arxiv.0802.0017
published in arXiv (Cornell University) (Cornell University) · 7 pages
arxiv created 2008/01/31 · openalex publication_date 2008/01/31 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
This paper presents a new technique for deterministic length reduction. This technique improves the running time of the algorithm presented in \citeLR07 for performing fast convolution in sparse data. While the regular fast convolution of vectors V1,V2 whose sizes are N1,N2 respectively, takes O(N1 log N2) using FFT, using the new technique for length reduction, the algorithm proposed in \citeLR07 performs the convolution in O(n1 log3 n1), where n1 is the number of non-zero values in V1. The algorithm assumes that V1 is given in advance, and V2 is given in running time. The novel technique presented in this paper improves the convolution time to O(n1 log2 n1) \sl deterministically, which equals the best running time given achieved by a \sl randomized algorithm. The preprocessing time of the new technique remains the same as the preprocessing time of \citeLR07, which is O(n12). This assumes and deals the case where N1 is polynomial in n1. In the case where N1 is exponential in n1, a reduction to a polynomial case can be used. In this paper we also improve the preprocessing time of this reduction from O(n14) to O(n13\rm polylog(n1)).