<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">DEPARTMENT OF COMPUTER SCIENCE<br><br>UNIVERSITY OF CHICAGO<br><br>Date: Monday, March 10, 2007<br>Time: 2:30 p.m.<br>Place: Ryerson 251, 1100 E. 58th Street<br><br>--------------------------------------------------<br><br>Speaker:<span class="Apple-tab-span" style="white-space: pre; "> </span>Mihai Patrascu<br><br>From:<span class="Apple-tab-span" style="white-space: pre; "> </span><span class="Apple-tab-span" style="white-space: pre; "> </span>MIT<br><br>Web page:<span class="Apple-tab-span" style="white-space: pre; "> </span><a href="http://web.mit.edu/~mip/www/">http://web.mit.edu/~mip/www/</a><br><br>Title: Limits of Data Structure<br><br>Abstract:<span class="Apple-tab-span" style="white-space: pre; "> </span> Over the years, theoretical computer science has been <br>vastly more successful at producing positive results (algorithms, <br>reductions) than negative ones ("SAT cannot be solved in polynomial <br>time"). In fact, our understanding of lower bounds is so limited that, <br>until recently, we failed to show:<br><br>* any Omega(lg n) lower bound, matching trivial upper bounds via <br>binary search trees.<br><br><br>* that a data structure of size O(n^100) is ever better than one of <br>size O(n).<br><br> In this talk, we prove such lower bounds by two simple, yet <br>surprising ideas. These techniques have been used to understand <br>several central problems (such as IP lookup in Internet routers), and <br>answer open questions dating back to 1989.<br><br>-----------------------------------------------<br><br>Host: Laci Babai<br></body></html>