In this talk, we discuss the known consequences of SETH and OVC failing. We then strengthen the evidence for these hardness assumptions, by showing that:
- If OVC fails then the Min-Weight k-Clique problem has faster than brute-force algorithms, even on hypergraphs.
- If SETH fails then not only formulas in conjunctive normal form have faster than brute-force algorithms, but even sparse TC^0 circuits (i.e., circuits on n variables, O(n) wires, depth O(1), and negation, AND, OR, and threshold gates).