ov_conjecture (363B)
1 # OV-conjecture 2 3 OV conjecture statement: we assume that we need time Omega(n^{2-o(1)}) to solve the [orthogonal_vectors] problem 4 5 Variant: [k_ov_conjecture] 6 7 We know that [seth_implies_ov] (since 2005) 8 9 This is equivalent to the [batch_partial_match_hypothesis] 10 11 Up: [computational_hypothesis] on [orthogonal_vectors] 12 13 See also: [omv], [fine_grained_complexity]