More consequences of falsifying SETH and the orthogonal vectors conjecture
More consequences of falsifying SETH and the orthogonal vectors conjecture
The Strong Exponential Time Hypothesis and the OV-conjecture are two popular hardness assumptions used to prove a plethora of lower bounds, especially in the realm of polynomial-time algorithms. The OV-conjecture in moderate dimension states there is no ε>0 for which an O(N2−ε) poly(D) time algorithm can decide whether there is …