[Theory] REMINDER: 1/3 Talks at TTIC: Omri Ben-Eliezer, Tel Aviv University

[Mary Marre]

*When:*      Friday, January 3rd at 11:00 am



*Where:*     TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526



*Who: *       Omri Ben-Eliezer, Tel Aviv University


*Title:*
The Quest for Adaptivity in Highly Structured Settings

*Abstract:*
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.
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.

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?

Based on joint works with Clément Canonne, Shoham Letzter and Erik
Waingarten.


*Host: *Madhur Tulsiani <madhurt at ttic.edu>


Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*


On Fri, Dec 27, 2019 at 2:20 PM Mary Marre <mmarre at ttic.edu> wrote:

> *When:*      Friday, January 3rd at 11:00 am
>
>
>
> *Where:*     TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526
>
>
>
> *Who: *       Omri Ben-Eliezer, Tel Aviv University
>
>
> *Title:*
> The Quest for Adaptivity in Highly Structured Settings
>
> *Abstract:*
> 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.
> 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.
>
> 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?
>
> Based on joint works with Clément Canonne, Shoham Letzter and Erik
> Waingarten.
>
>
> *Host: *Madhur Tulsiani <madhurt at ttic.edu>
>
>
>
>
> Mary C. Marre
> Administrative Assistant
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue*
> *Room 517*
> *Chicago, IL  60637*
> *p:(773) 834-1757*
> *f: (773) 357-6970*
> *mmarre at ttic.edu <mmarre at ttic.edu>*
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20200102/649c856b/attachment.html>