[Colloquium] Mihai Patrascu, MIT- TTI-C Talk
Julia MacGlashan
macglashan at tti-c.org
Fri Apr 18 14:12:45 CDT 2008
When: Tuesday, April 22 @ 2:30pm
Where: TTI-C Conference Room
Who: Mihai Patrascu, MIT
Topic: DATA STRUCTURES
We show that a large fraction of the data-structure lower bounds known today
in fact follow by reduction from the communication complexity of lopsided
(asymmetric) set disjointness! This includes lower bounds for:
* high-dimensional problems, where the goal is to show large space lower
bounds.
* constant-dimensional geometric problems, where the goal is to bound the
query time for space O(n.polylg n).
* dynamic problems, where we are looking for a trade-off between query and
update time. (In this case, our bounds are slightly weaker than the
originals, losing a lglgn factor.)
Our reductions also imply new lower bounds for range reporting, the partial
match problem, and reachability oracles.
Contact: Prahladh Harsha, TTI-C prahladh at tti-c.org
834-2549
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20080418/6e8e3b84/attachment.html
More information about the Colloquium
mailing list