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