# What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?

Last year I had watched this talk online about problems in $P$ for which an algorithm which runs in some subclass of $P$, say in subquadratic time, would imply $P = NP$, or violate the ETH (exponential time hypothesis). I cannot find this talk and am interested in said problems, for I want to look into quantum algorithms for this group of problems during the semester I'm beginning right now.

She explains (starting at 42:30 in the video) that if there is a $O\left(n^{2-\varepsilon}\right)$ algorithm for some $\varepsilon>0$ for the Orthogonal Vectors problem, then the Strong Exponential Time Hypothesis (SETH) is false. This would not immediately imply $P=NP$, but it would show an $O\left(2^{n-\epsilon}\right)$ algorithm for every $k$-SAT, which would be better than what we have right now; right now we have algorithms which solve $k$-SAT in $2^{n-O\left(\frac{1}{k}\right)}$, so these algorithms tend to $2^{n}$ for large $k$.