Aarhus University Seal

Higher Cell Probe Lower Bounds for Evaluating Polynomials

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

In this paper, we study the cell probe complexity of evaluating an $n$-degree polynomial $P$ over a finite field $F$ of size at least $n^{1+Omega(1)}$. More specifically, we show that any static data structure for evaluating $P(x)$, where $x in F$, must use $Omega(lg |F|/lg(Sw/nlg|F|))$ cell probes to answer a query, where $S$ denotes the space of the data structure in number of cells and $w$ the cell size in bits. This bound holds in expectation for randomized data structures with any constant error probability $delta
Original languageEnglish
Title of host publicationFOCS'12: IEEE 53rd Annual Symposium on Foundations of Computer Science
Number of pages9
PublisherIEEE Computer Society Press
Publication year2012
Pages293 - 301
ISBN (print)978768548746
Publication statusPublished - 2012
EventAnnual Symposium on Foundations of Computer Science - TBD, New Brunswick, NJ, United States
Duration: 20 Oct 201223 Oct 2012
Conference number: 53


ConferenceAnnual Symposium on Foundations of Computer Science
LandUnited States
ByNew Brunswick, NJ

See relations at Aarhus University Citationformats

ID: 45939822