STOC 2015 Tutorial: Hardness and Equivalences in P

Tutorial: Hardness and Equivalences in P
Date: Sunday, June 14, 2015 Location: STOC 2015, Oregon Convention Center, Portland, Oregon Room E143-144, find it on the MAP Speakers: Amir Abboud, Arturs Backurs, Piotr Indyk and Virginia V. Williams Description: 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. 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 tutorial is to expose the general theory community 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. Schedule: 11:20-12:30pm Overview - slides Lunch Break 2-3pm Lower bounds and equivalences for graph problems - slides 3-3:30pm Lower bounds for dynamic algorithms - slides Coffee break 4-4:30pm Overview on sequence problems - slides 4:30-5pm Lower bounds for sequence problems - slides 5-5:30pm Conclusion and future work - slides

Tutorial: Hardness and Equivalences in P

Date: Sunday, June 14, 2015
Location: STOC 2015, Oregon Convention Center, Portland, Oregon
Room E143-144, find it on the MAP

Speakers: Amir Abboud, Arturs Backurs, Piotr Indyk and Virginia V. Williams

Description: 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.

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 tutorial is to expose the general theory community 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.

Schedule:
11:20-12:30pm Overview - slides
Lunch Break
2-3pm Lower bounds and equivalences for graph problems - slides
3-3:30pm Lower bounds for dynamic algorithms - slides
Coffee break
4-4:30pm Overview on sequence problems - slides
4:30-5pm Lower bounds for sequence problems - slides
5-5:30pm Conclusion and future work - slides