Almost quadratic gap between partition complexity and query/communication complexity.

Andris Ambainis

Published in: Electron. Colloquium Comput. Complex. (2015)

Keyphrases

computational complexity
database
space complexity
co occurrence
communication cost
decision problems
worst case
multi dimensional
retrieval method
communication networks
user defined
information sharing
retrieval systems
computational cost
relational databases
pairwise
data structure
multimedia