Stefan Schneider (Theory Seminar)

schneider.jpg"Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility"
Stefan Schneider
Monday, May 9th, 2016, 2:00 pm
EBU3B, Room 4258
We introduce the Nondeterministic Strong Exponential Time Hypothesis  (NSETH) as a natural extension of the Strong Exponential Time Hypothesis (SETH). We show that both refuting and proving NSETH would have interesting consequences.
In particular we show that disproving NSETH would give new nontrivial circuit lower bounds. On the other hand, NSETH implies non-reducibility results, i.e. the absence of (deterministic) fine-grained reductions from SAT to a number of problems. As a consequence we conclude that unless this hypothesis fails, problems such as 3-Sum, APSP and model checking of a large class of first-order graph properties  cannot be shown to be SETH-hard using deterministic or zero-error probabilistic reductions.

Joint work with Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin and Ramamohan Paturi

Paper Link

Related: Final Defense of Stefan Schneider's Ph.D. dissertation in June 2017.