2015/01/20 by Andrew Arnold, Arnold, Andrew, Daniel S. Roche +1 · 1 citation
Computer Science · Mathematics · #12Y05 #68Q17 #68W20 #68W30 #Algorithm #Analytic Number Theory Research #Coding theory and cryptography #Combinatorics #Computational Complexity (cs.CC) #Computer science #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #Discrete mathematics #F.2.1 #F.2.3 #FOS: Computer and information sciences #G.3 #G.4 #I.1.2 #Integer (computer science) #Interpolation (computer graphics) #Mathematics #Multiplication (music) #Multivariate statistics #Polynomial #Polynomial and algebraic computation #Set (abstract data type) #Symbolic Computation (cs.SC) #Univariate #acm:12Y05 #acm:68Q17 #acm:68W20 #acm:68W30 #cs.CC #cs.DS #cs.SC #msc:12Y05 #msc:68Q17 #msc:68W20 #msc:68W30
paper · pdf · doi:10.48550/arxiv.1501.05296
published in arXiv (Cornell University) (Cornell University) · Submitted to ISSAC 2015
openalex publication_date 2015/01/20 · arxiv created 2015/04/24 · arxiv updated 2015/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
We present randomized algorithms to compute the sumset (Minkowski sum) of two\ninteger sets, and to multiply two univariate integer polynomials given by\nsparse representations. Our algorithm for sumset has cost softly linear in the\ncombined size of the inputs and output. This is used as part of our sparse\nmultiplication algorithm, whose cost is softly linear in the combined size of\nthe inputs, output, and the sumset of the supports of the inputs. As a\nsubroutine, we present a new method for computing the coefficients of a sparse\npolynomial, given a set containing its support. Our multiplication algorithm\nextends to multivariate Laurent polynomials over finite fields and rational\nnumbers. Our techniques are based on sparse interpolation algorithms and\nresults from analytic number theory.\n