Miltersen, Peter Bro (1995) On the cell probe complexity of polynomial evaluation. Theoretical Computer Science, Volume 143 (Number 1). pp. 167-174. doi:10.1016/0304-3975(95)80032-5

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

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
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title:	Theoretical Computer Science
Publisher:	Elsevier Science BV
ISSN:	0304-3975
Official Date:	10 July 1995
Dates:	Date Event 10 July 1995 Published
Volume:	Volume 143
Number:	Number 1
Number of Pages:	8
Page Range:	pp. 167-174
DOI:	10.1016/0304-3975(95)80032-5
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Version or Related Resource:	Miltersen, P.B. (1994). On the cell probe complexity of polynomial evaluation. University of Warwick. Department of Computer Science. (Department of Computer Science research report, 267).
Related URLs:	Related item in WRAP

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item