## Hardness in P (an overview)

by Amir Abboud

#### Oded's comments

This talk provided a good overview of the study of the attempts
to provide conditional lower bounds for various problems in P.
Amir presented four (non-disjoint) types
of hardness results (or rather classes of problems),
grouped according to the assumption/conjectured used.
These iclude SETH-hardness (i.e., assuming that $n$-vriable
SAT instances cannot be solved in time $c^n$ for $c<2$),
3SUM-hardness (i.e., assuming that 3SUM has no
sub-quadratic (i.e., $n^c$ for $c<2$) time algorithms),
APSP-hardness (i.e., assuming that all-pairs shortest path
cannot be solved in sub-cubic time),
and the $k$-clique conjecture
(which refers to beating the best algorithms known).

#### 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.
I will present the most recent landscape of P and the conjectures on which
this project is based on (e.g. the Strong Exponential Time Hypothesis). I
will discuss recent attempts on identifying new conjectures: either more
reliable ones, or ones that will get us closer to a full classification of
the important problems in P.
Finally, I will highlight a surprising new reduction from Circuit-SAT to
natural problems in P like Edit-Distance which proves that minor improvements
over the quadratic running time of Edit-Distance are enough to prove major
complexity separations.

Back to
list of Oded's choices.