<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div class=""><div class=""><b class="" style="background-color: rgba(255, 255, 255, 0);">Alexander Golovnev</b></div><div class=""><b class="" style="background-color: rgba(255, 255, 255, 0);">Harvard University</b></div><div class=""><b class="" style="background-color: rgba(255, 255, 255, 0);"><br class=""></b></div><div class=""><b class=""><a href="x-apple-data-detectors://1" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="1" style="text-decoration-color: rgba(0, 0, 0, 0.258824); background-color: rgba(255, 255, 255, 0);">Tuesday, November 12, 2019</a></b></div><div class=""><b class="" style="background-color: rgba(255, 255, 255, 0);">Ryerson 251 <a href="x-apple-data-detectors://2" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="2" style="text-decoration-color: rgba(0, 0, 0, 0.258824);">@ 3:30pm</a></b></div></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);"><br class=""></span></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);"><b class="">Title: Static Data Structure Lower Bounds Imply Rigidity</b><br class=""></span></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);"><br class=""></span></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);">Abstract: We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of t > omega(log^2 n) on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small linear space (s = (1 + eps)n), would already imply a semi-explicit (P^NP) construction of rigid matrices <span class="gmail-il">with</span> significantly better parameters than the current state of art (Alon, Panigrahy <span class="gmail-il">and</span> Yekhanin, 2009). Our results further assert that polynomial (t ≥ n^delta) data structure lower bounds against near-optimal space, would imply super-linear circuit lower bounds for log-depth linear circuits (a four-decade open question). In the succinct space regime (s = n + o(n)), we show that any improvement on current cell-probe lower bounds in the linear model would also imply new rigidity bounds. Our results rely on a new connection between the “inner” <span class="gmail-il">and</span> “outer” dimensions of a matrix (Paturi <span class="gmail-il">and</span> Pudlak, 2006), <span class="gmail-il">and</span> on a new reduction from worst-case to average-case rigidity, which is of independent interest.<br class=""></span></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);"><br class=""></span></div><div class=""><span style="background-color: rgba(255, 255, 255, 0);">Joint work with Zeev Dvir and Omri Weinstein.</span></div><div dir="ltr"></div></body></html>