[Colloquium] Mihai Patrascu, MIT- TTI-C Talk

[Julia MacGlashan]

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/20080421/0c2a8a68/attachment.html