<div dir="ltr"><div class="gmail_default" style="font-size:small"><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Friday, January 3rd at 11:00 am</font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"><span class="gmail-il">TTIC</span>, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b>       </font></font></font>Omri Ben-Eliezer, Tel Aviv University</p></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><div><b>Title:</b><br>The Quest for Adaptivity in Highly Structured Settings<br><br><b>Abstract:</b><br>Recent years have seen a large number of devastating lower bounds for sublinear algorithms in highly structured settings, both in theory and in practice. Without a substantial amount of adaptivity, even relatively simple problems in this context suffer from inherent barriers like the curse of dimensionality or from prohibitive lower bounds for commonly employed heuristics. </div><div>On the other hand, these limitations do not apply to adaptive algorithms, and it is widely conjectured that for many central problems in this field, adaptive algorithms are much (sometimes even exponentially) faster than their non-adaptive counterparts. However, adaptive algorithms are typically difficult to obtain, as they require good structural understanding of the problem at hand.<br><br>In this talk, I will survey a few recent results on this topic. I will then focus on a specific line of work on sublinear algorithms for pattern detection in sequential data, which showcases many of the phenomena described above. The results are closely related to classical algorithmic string problems like the LIS (longest increasing subsequence) and monotonicity testing. They include a powerful structural dichotomy for sequences, useful for algorithmic purposes; optimal adaptive (and non-adaptive) techniques to utilize this structural understanding in an important special case, which lead to surprising and tight bounds on the query complexity; and a new combinatorial, seemingly strange fine-grained parameter of permutations that naturally appears in this problem, showing that non-adaptive algorithms are generally very weak for most patterns. The most interesting question, however, remains open: can adaptivity yield an exponential speedup?<br><br>Based on joint works with Clément Canonne, Shoham Letzter and Erik Waingarten.</div><div><br></div><div><br></div><div><b>Host: </b><a href="mailto:madhurt@ttic.edu">Madhur Tulsiani</a></div><div><br></div><div><br></div><div><br></div><div><br></div></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>