MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture

Karl Bringmann
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, MMCI  
AG Audience
English

Date, Time and Location

Thursday, 15 March 2018
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

The Strong Exponential Time Hypothesis and the Orthogonal Vectors Conjecture are two popular hardness assumptions used to prove a plethora of time complexity lower bounds, for diverse problems on strings, graphs, etc. in the exponential as well as the polynomial time world. That is, if these assumptions hold they have a huge explanatory power. However, what reasons do we have to believe these assumptions? What would happen if these assumptions were wrong?

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

Contact

Karl Bringmann
--email hidden
passcode not visible
logged in users only

Karl Bringmann, 02/28/2018 09:37 PM -- Created document.