Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Miltersen, Peter Bro
Publisher: University of Warwick. Department of Computer Science
Journal: Theoretical Computer Science
Languages: English
Types: Article
Subjects: QA, Theoretical Computer Science, Computer Science(all)

Classified by OpenAIRE into

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) ).
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] E.Cf . Belaga. F-r'aluation of poll'nonrials of ont' r'ariable w it h prelirnirrarl lrrocessing of tlie coefficients. Ploblrrny It-ibrrne t. 5 (1901) 7-15.
    • [t] \1.L. Frerlman. J. Koml6s, E. Szenrer6di, Storing a sparse table rvith O(1) \\'orst case access tirne. J. Assoc. Compul.. ,llach.3l (1981) 538-541.
    • [6] \1.L. Freclnrau. \1.E. Saks, The cell probe complexitl'of cl1'narnic data structures. in: Proc.2lsl Ann..4C:,\I Syntp. on Thtnry of Cotrtpuling (1989) 3-1ir-35.1.
    • [i] D.E. Knuth. Thr .4rt of Cortpuler Programming. \-ol. II: Scnrinunttrical Algorithnts (Addison-\\'esley. Reading. trlA. 2nd ed.. 1980).
    • [8] P.B. \liltersen. The bit probe corrrplexit,r'rleasure revisited. in: Proc. 10th Syntlt. on I'he oretical Aspecls of Compuler Scitnce. Lecture Notes in C'ornputer Science. \Iol. 665 (Springer, Berlin. 1993) 662-671.
    • [9] P.B. \liltersen. Lorver bounds for I--nion-Split-Find related probletns on rarrdonr access nrachines, to appear in: Proc. 26lh ,|nn. ACtrI Sgnrp. on Theory of C'ontpuling (199a).
    • [10] P.B. ]liltersen. S. Subran.ranian. J.S. Vitter. R. fanrassia. Clonrplexit]- nrodels for increnrental conrputation. TArorelical C'ompuler Sclrncr. to appear.
    • [11] \'. \a. Pan. \lethods of corrrputing values of poly'nomia]s, r?ussian ,l.fo1i. 5rrrlrys 21 (1) (1966) 105-136.
    • [12] A.C. \-ao. Sonre cornplexity' questions related to distributive cor.r.rputing. in; Proc. 11th .|nn. AC')I Syntp. on Theorg of Computirtg (1979) 209-213.
    • [13] A.C. \ao. Should tables be sorted?. J. Assoc. Conpul. JIach.28 (1981) 6 1 5-628.
  • No related research data.
  • No similar publications.
  • BioEntity Site Name
    2lslProtein Data Bank