## 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.