Hardness for Graph Problems - Reductions Based on APSP and SETH
Calvin Lab Auditorium
The first session of this talk will take place on Tuesday, September 1 from 9:30 am – 10:30 am; the third session of this talk will take place on Thursday, September 3 from 1:30 pm – 2:30 pm; the fourth session of this talk will take place on Friday, September 4 from 11:00 am – 12:00 pm.
A central goal of theoretical computer science is the classification of computational problems according to their complexity. The theory of NP-hardness has been successful in identifying problems that are unlikely to be solvable in time that is polynomial in the size of the input. Conversely, for many problems of practical interest, the field has developed intriguingly fast polynomial time solutions. However, improving the running times of many of these algorithms has been a longstanding open problem, with little to no progress. It is thus completely plausible that these algorithms are optimal. Showing that this is indeed the case would be a great accomplishment of the theory of algorithms.
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.
