Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider

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

Oded Goldreich, Guy Rothblum

For every polynomial $q$, we present worst-case to average-case (almost-linear-time) reductions for a class of problems in $\cal P$ that are widely conjectured not to be solvable in time $q$.

These classes contain, for example, the problems of counting the number of $k$-cliques in a graph, for any fixed $k\geq3$.

more >>>