Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems

The first non-trivial time-space tradeoff lower bounds have been shown for decision problems in P using notions derived from the study of two-party communication complexity. These results are proven directly for branching programs, natural generalizations of decision trees to directed graphs that pr...

Full description

Saved in:
Bibliographic Details
Main Authors: Beame, P., Vee, E.
Format: Conference Proceeding
Language:English
Subjects:
Binary decision diagrams
Boolean functions
Complexity theory
Computational complexity
Computer science
Data structures
Decision trees
Extraterrestrial measurements
Nearest neighbor searches
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The first non-trivial time-space tradeoff lower bounds have been shown for decision problems in P using notions derived from the study of two-party communication complexity. These results are proven directly for branching programs, natural generalizations of decision trees to directed graphs that provide elegant models of both non-uniform time T and space S simultaneously. We develop a new lower bound criterion, based on extending two-party communication complexity ideas to multiparty communication complexity. Applying this criterion to an explicit Boolean function based on a multilinear form over F/sub 2/. for suitable s, we show lower bounds that yield T = /spl Omega/(n log/sup 2/ n) when S /spl les/ n/sup 1-/spl epsi// log |D| for large input domain D. Finally, we develop lower bounds for nearest-neighbor problems involving n data points in a variety of d-dimensional metric spaces.
ISSN:1093-0159
2575-8403
DOI:10.1109/CCC.2002.1004330