2018/05/21 by Pavel Emelyanov, Emelyanov, Pavel, Denis Ponomaryov +1
Computer Science · #Algorithms and Data Compression #Coding theory and cryptography #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Methods in Verification #Polynomial and algebraic computation #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.1805.08186
openalex publication_date 2018/05/21 · openalex created_date 2022/09/30 · openalex updated_date 2026/07/28
In 2010, A. Shpilka and I. Volkovich established a prominent result on the\nequivalence of polynomial factorization and identity testing. It follows from\ntheir result that a multilinear polynomial over the finite field of order 2 can\nbe factored in time cubic in the size of the polynomial given as a string.\nLater, we have rediscovered this result and provided a simple factorization\nalgorithm based on computations over derivatives of multilinear polynomials.\nThe algorithm has been applied to solve problems of compact representation of\nvarious combinatorial structures, including Boolean functions and relational\ndata tables. In this paper, we describe an improvement of this factorization\nalgorithm and report on preliminary experimental analysis.\n