Conditional Lower Bounds for Algorithms with Pre-processed Advice

This talk explores data structures for algorithmic tasks that utilize pre-processing phases, focusing on the tradeoffs between query-time resources and pre-processing resources like preparation time and storage size. Examine conditional lower bounds for such problems based on the conjectured hardness of 3SUM Indexing, SetDisjointness, and Reachability as studied in key research papers. Follow along as Manideep Manindlapally surveys classical results from these papers and outlines potential directions toward quantum versions of these lower bounds, offering insights into an alternative approach to algorithm analysis beyond traditional space-time resource minimization.