Jump to content

Cell-probe model

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Simonpratt (talk | contribs) at 02:56, 9 April 2014 (Removed old content, added headings for cell-probe model, some cell-probe model content). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

This sandbox is in the article namespace. Either move this page into your userspace, or remove the {{User sandbox}} template. In computer science, the cell-probe model is a model of computation in which cost is only associated with memory access.

TODO

Formal definition

TODO[1]


Notable results

Dynamic Partial Sums

Mihai Pătraşcu showed that the partial sums problem requires time per operation.[2]

TODO

See also

References

  1. ^ Yao, Andrew Chi-Chih (July 1981). "Should Tables Be Sorted?". J. ACM. 28 (3): 615--628. doi:10.1145/322261.322274.
  2. ^ Pătraşcu, Mihai (2006). "Logarithmic lower bounds in the cell-probe model". SIAM Journal on Computing. 35 (4): 932--963. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Cell-probe_model&oldid=603393811"