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
Note: We use this to send email in the morning.
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 21:37 -- Created document.