Stem unless$ (all stems)

4 papers:

STOC-2015-BackursI #distance #edit distance

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) (AB, PI), pp. 51–58.

STOC-2010-DellM #polynomial #satisfiability

Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses (HD, DvM), pp. 251–260.

DATE-2007-WittmannVWNKFM #question

Life begins at 65: unless you are mixed signal? (RW, MV, HJW, NN, JK, JEdF, CM), pp. 936–941.

STOC-1999-KlivansM #graph #morphism #polynomial #proving

Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses (AK, DvM), pp. 659–667.