Abstract-I detta papper, studerar vi cellproben komplexiteten i att utvärdera en n-grad polynom P över ett ändligt fält F i storlek minst n 1 +.(1). Mer specifikt visar vi att varje statisk datastruktur för att utvärdera P (x), där x  på F, måste använda cellsonder för att svara på en fråga, där S betecknar utrymmet för datastrukturen i antal celler och w cellstorleken i bitar. Denna gräns håller i förväntan på randomiserade datastrukturer med konstant felsannolikhet δ < 1/2. Vår nedre gräns förbättras inte bara över den nedre gränsen av Miltersen [TCS' 95], utan är i själva verket den högsta statiska cellsonden lägre än hittills: För linjärt utrymme (dvs. S = O(n lg -f/w)), förenklar vår frågetid lägre gräns till -g (lg-lg-lg-d), medan den högsta tidigare nedre gränsen för eventuella problem med statisk datastruktur med d-olika frågor är -(lg-d/lg-d), som först uppnåddes av P-traşcu och Thorup [SICOMP'10]. Vi använder också den senaste tekniken av Larsen [STOC'12] för att visa en lägre gräns av tq =  och (lg  till F till lg n/ lg(wtu/ lg  till F) lg(wtu)) för dynamiska datastrukturer för polynom utvärdering över ett ändligt fält F i storlek 2 ). Här tq betecknar den förväntade frågetiden och tu det värsta fallet uppdateringstid. Denna nedre gräns gäller för slumpmässiga datastrukturer med konstant felsannolikhet δ < 1/2. Detta är bara andra gången en lägre gräns bortom max{tu, tq} =  och (max{lg n, lg d/ lg lg d}) har uppnåtts för dynamiska datastrukturer, där d anger antalet olika frågor och uppdateringar av problemet. Dessutom är det den första så lägre gränsen som håller för randomiserade datastrukturer med konstant sannolikhet för fel.
Den nedre gränsen i REF håller faktiskt för icke-deterministiska cellsonder, dvs. certifikat.
Higher Cell Probe Lower Bounds for Evaluating Polynomials
{'venue': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'journal': '2012 IEEE 53rd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}