Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Speaker:Karl Bringmann
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 15 March 2018
Duration:30 Minutes
Building:E1 4
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).

Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Karl Bringmann, 02/28/2018 09:37 PM
Last modified:
Uwe Brahm/MPII/DE, 03/15/2018 07:01 AM
  • Karl Bringmann, 02/28/2018 09:37 PM -- Created document.