Hardness in P (survey talk)

by Amir Abboud

Oded's comments

This is a fantastic talk. It provides a view of four classes of natural problems within P, where each class consists of problems that do not seem to have almost linear time algorithms (in the most relaxed sense of this term). The classes are defined in terms of the evidence provided for the latter belief:

SETH (Strong Exp-Time Hypo.):
no $2^{cn}$-time algorithm for SAT for any constant $c<1$ (or, a lower bound of $2^{c_k n}$ for k-SAT, where $c_k$ approaches 1 with $k$
The 3SUM conjecture:
no $n^c$ algorithm for 3SUM (finding three elements in a sequence that sum-up to zero) for any constant $c<2$.
The APSP conjecture:
no $n^c$ algorithm for All Pairs Shortest Paths for any constant $c<3$.
The k-CLIQUE conjecture:
no $n^{ck}$ lagorithm for $k$-Clique for any constant $c$ smaller than one third of the exponent of Boolean matrix multiplication.
A host of natural computational problems falls into these classes, but some still remain to be classified. In addition to presenting the known classification map, Amir discussed future directions, which include providing additional support for the conjectures (and/or relating them or variants of them), dealing with the hardness result (e.g., seeking approximations or average-case analysis or anaylisis of natural resteruictions of the input) and considering other complexity measures (e.g., space).

The original abstract

The class P attempts to capture the efficiently solvable computational tasks. It is full of practically relevant problems, with varied and fascinating combinatorial structure.

In this talk, I will give an overview of a rapidly growing body of work that seeks a better understanding of the structure within P. Inspired by NP-hardness, the main tool in this approach are combinatorial reductions. Combining these reductions with a small set of plausible conjectures, we obtain tight lower bounds on the time complexity of many of the most important problems in P.

(Slides may be posted at a later time; hopefully, soon.)

Back to list of Oded's choices.