<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-267

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

Per Bro Miltersen, On the Cell Probe Complexity of Polynomial Evaluation (April 1, 1994).

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) ).

<%@ include file="cited.html" %>

P.B. Miltersen, "On the Cell Probe Complexity of Polynomial Evaluation", Theoretical Computer Science 143(1), pp. 167-174 (1995)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>