Statements (21)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
|
| gptkbp:analyzes |
number of memory cell accesses
|
| gptkbp:appliesTo |
dynamic data structures
static data structures |
| gptkbp:assumes |
arbitrary computation between probes
|
| gptkbp:focusesOn |
memory access complexity
|
| https://www.w3.org/2000/01/rdf-schema#label |
cell-probe model
|
| gptkbp:ignores |
computation cost
|
| gptkbp:introduced |
gptkb:Andrew_Yao
|
| gptkbp:introducedIn |
1981
|
| gptkbp:relatedTo |
pointer machine model
word RAM model |
| gptkbp:studies |
query complexity
update complexity |
| gptkbp:usedFor |
lower bound proofs
|
| gptkbp:usedIn |
data structure analysis
|
| gptkbp:uses |
lower bounds for dynamic connectivity
lower bounds for predecessor problem lower bounds for range searching |
| gptkbp:bfsParent |
gptkb:Mihai_Pătrașcu
|
| gptkbp:bfsLayer |
5
|