𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the cell probe complexity of polynomial evaluation

✍ Scribed by Peter Bro Miltersen

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
461 KB
Volume
143
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the polynomial IO-complexity
On the polynomial IO-complexity
✍ JosΓ©D.P. Rolim πŸ“‚ Article πŸ“… 1989 πŸ› Elsevier Science 🌐 English βš– 808 KB
The bit-operation complexity of approxim
The bit-operation complexity of approximate evaluation of matrix and polynomial products using modular arithmetic
✍ V. Pan πŸ“‚ Article πŸ“… 1982 πŸ› Elsevier Science 🌐 English βš– 330 KB

The approximate evaluation with a given precision of matrix and polynomial products is performed using modular arithmetic. The resulting algorithms are numerically stable. At the same time they are as fast as or faster than the algorithms with arithmetic operations over real or complex numbers.

The complexity of the characteristic and
The complexity of the characteristic and the minimal polynomial
✍ Thanh Minh Hoang; Thomas Thierauf πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 188 KB

We investigate the complexity of (1) computing the characteristic polynomial, the minimal polynomial, and all the invariant factors of an integer matrix, and of (2) verifying them, when the coe cients are given as input. It is known that each coe cient of the characteristic polynomial of a matrix A

On the Deterministic Complexity of Facto
On the Deterministic Complexity of Factoring Polynomials
✍ Shuhong Gao πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 345 KB

The paper focuses on the deterministic complexity of factoring polynomials over finite fields assuming the extended Riemann hypothesis (ERH). By the works of and , the general problem reduces deterministically in polynomial time to finding a proper factor of any squarefree and completely splitting