Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

On the cell probe complexity of polynomial evaluation

Tools
- Tools
+ Tools

Miltersen, Peter Bro (1994) On the cell probe complexity of polynomial evaluation. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)

[img]
Preview
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-267.pdf - Other - Requires a PDF viewer.

Download (618Kb) | Preview

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 != ncr - TIME (o (log n/ log log n) ).

Item Type: Report
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH): Polynomials
Series Name: Department of Computer Science research report
Publisher: University of Warwick. Department of Computer Science
Official Date: April 1994
Dates:
DateEvent
April 1994Completion
Number: Number 267
Number of Pages: 8
DOI: CS-RR-267
Institution: University of Warwick
Theses Department: Department of Computer Science
Status: Not Peer Reviewed
Publication Status: Unpublished
Publisher Statement: P.B.&nbsp;Miltersen, &ldquo;On the Cell Probe Complexity of Polynomial Evaluation&rdquo;, <i>Theoretical Computer Science</i> <b>143</b>(1), pp.&nbsp;167-174 (1995)
Funder: Forskningsrådet for Natur og Univers [Danish Science Research Council] (FNU), European Strategic Programme of Research and Development in Information Technology (ESPRIT)
Grant number: 7141 (ESPRIT)
Version or Related Resource: Miltersen, P.B. (1995). On the cell probe complexity of polynomial evaluation. Theoretical Computer Science, 143(1). pp. 167-174.
Related URLs:
  • Organisation
  • Related item in WRAP

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us