Calvin Lab Auditorium
The first session of this talk will take place on Tuesday, September 1 from 9:30 am – 10:30 am; the second session of this talk will take place on Wednesday, September 2 from 9:30 am – 10:30 am; the fourth session of this talk will take place on Friday, September 4 from 11:00 am – 12:00 pm.
Unfortunately, unconditional lower bounds seem hard to obtain. Instead, an alternative approach for proving hardness of problems in P is to identify plausible complexity-theoretic conjectures and show that the currently best algorithms for the problems of interest are optimal if one assumes these conjectures. Such popular conjectures include the (Strong) Exponential Time Hypothesis (that concerns the complexity of CNF-SAT), the conjecture that all-pairs shortest paths (APSP) requires essentially cubic time, or that 3SUM requires essentially quadratic time.
The goal of the minicourse is to expose the audience to the recent growing body of conditional lower bounds for a variety of problems in diverse areas, such as graph optimization, string matching, geometry, and dynamic data structures, and to the attempts at unifying and/or refuting the popular conjectures.