arXiv preprint ·
Fast Evaluation of Polynomials with Rational Preprocessing
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Horner's rule evaluates a monic degree-$n$ polynomial using $n-1$ multiplications. We show that with rational preprocessing of the coefficients, any such polynomial can be evaluated using only $\lfloor n/2 \rfloor + 1$ multiplications over fields of characteristic zero or of characteristic $p>n$. This resolves the multiplication side of a conjecture of Rabin and Winograd (Comm. Pure Appl. Math 1972), who achieved $n/2 + 2\lceil\log_2 n\rceil$ multiplications and conjectured the logarithmic overhead was necessary. We show that this multiplication count can't be beaten in general, proving that three multiplications do not suffice for degree~$6$. This strengthens the lower bound of Pan (STOC 1978), who proved a tight bound for general, complex preprocessing. In characteristic~2, for every $n>1$ and every finite field of size at least $2n$, we prove that an $n$-multiplication chain cannot parametrize all value vectors at $2n$ distinct evaluation points, even with arbitrary preprocessing. We give $\lfloor n/2 \rfloor + 1$ multiplication schedules over characteristic~2, each with an explicit inverse, for every odd degree $n\le 25$ and conjecture that this is possible for all $n$. We also give an injective polynomial construction for universal hashing that uses $N$ multiplications to hash $2N$ values with a single random key. This improves the best previous construction by Daniel J. Bernstein (cryp.to).
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Polynomial Lower Bounds for Distributed Graph Sketching with Tiny Error: Connectivity and Spanning Tree Construction
1.73-Optimal Echelon Stock (R,nQ) Policies in Two-Stage Stochastic Serial Systems
Quantum Query Algorithms for the Constructive Diagonal Ramsey Theorem
Query-Oblivious Coresets for Softmax Attention: Improved Bounds and Efficient Constructions
Computation and Applications of Euclidean and Normed Representations of Massive Data
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.