# Lower-bounds under SETH

After reading a bit about SETH (the strong exponential time hypothesis), I see that a lot of lower bounds for problems in P can be proven if we assume SETH. But I notice that most of the ones that are proven are solved in quadratic time (or slower). I wonder if any linear or $$O(n\ log(n))$$ time problem can have a similar property?

Is this something we can ask/show? What do you think?

Most problems need at least linear time, so $$O(n \log n)$$ may be a little too close to optimal for a SETH based lower bound, generally we want running times where one can improve on the exponent by some constant.
However you can define problems solvable in $$n^{1.0001}$$ time such that improvements in the exponent would still refute SETH. Here is a simple example: consider Orthogonal Vectors with $$n$$ "red" vectors in $$O(\log n)$$ dimensions and $$n^{0.0001}$$ "blue" vectors in the same dimensions, and you want to find a red-blue pair that is orthogonal. It is not hard to see that improving over the obvious running time of this vector pair problem (in the exponent) would also refute SETH.