Conditional lower bounds for algorithms with pre-processed advice

Unlike the traditional study of algorithms which attempts to solve a certain task using minimal space and time resources, I will discuss data structures to solve certain algorithmic tasks after an initial pre-processing phase. The interest here is to study the tradeoffs between the resources such as the space and time required to perform the algorithmic task when asked a query; and the resources in the pre-processing phase such as the time required to prepare the data structure or its size.

In [1], [2] the authors study lower bounds for a class of such problems conditioned on the conjectured hardness of problems like 3SUM Indexing, SetDisjointness and Reachability. In my talk, I will survey the classical results from [1] and [2] and sketch a direction towards their quantum versions.

[1] http://arxiv.org/abs/1706.05847 

[2] http://arxiv.org/abs/1706.05815

 *We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*