Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
Thanks for any answers.
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.
