Manideep Manindlapally: Conditional lower bounds for algorithms with pre-processed advice
0Unlike 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