The Library
ON THE CELL PROBE COMPLEXITY OF POLYNOMIAL EVALUATION
Tools
Tools
Tools
UNSPECIFIED (1995) ON THE CELL PROBE COMPLEXITY OF POLYNOMIAL EVALUATION. [Journal Item]
Full text not available from this repository.Abstract
We consider the cell probe complexity of the polynomial evaluation problem with preprocessing of coefficients, for polynomials of degree at most n over a finite field K. We show that the trivial cell probe algorithm for the problem is optimal if K is sufficiently large compared to n. As an application, we give a new proof of the fact that P not equal incr-TIME (o(log n/log log n)).
| Item Type: | Journal Item |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Journal or Publication Title: | THEORETICAL COMPUTER SCIENCE |
| Publisher: | ELSEVIER SCIENCE BV |
| ISSN: | 0304-3975 |
| Date: | 29 May 1995 |
| Volume: | 143 |
| Number: | 1 |
| Number of Pages: | 8 |
| Page Range: | pp. 167-174 |
| Publication Status: | Published |
| URI: | http://wrap.warwick.ac.uk/id/eprint/19787 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
