2025/07/15 by Anita Dürr, Dürr, Anita, Evangelos Kipouridis +4 · 1 citation
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Coding theory and cryptography #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2507.11098
openalex publication_date 2025/07/15 · openalex created_date 2025/10/08 · openalex updated_date 2026/07/28
In the Orthogonal Vectors problem (OV), we are given two families A, B of subsets of \1,…,d\, each of size n, and the task is to decide whether there exists a pair a ∈ A and b ∈ B such that a ∩ b = ∅. Straightforward algorithms for this problem run in O(n2 ⋅ d) or O(2d ⋅ n) time, and assuming SETH, there is no 2o(d)⋅ n2-ε time algorithm that solves this problem for any constant ε > 0. Williams (FOCS 2024) presented a O(1.35d ⋅ n)-time algorithm for the problem, based on the succinct equality-rank decomposition of the disjointness matrix. In this paper, we present a combinatorial algorithm that runs in randomized time O(1.25d n). This can be improved to O(1.16d ⋅ n) using computer-aided evaluations. We generalize our result to the k-Orthogonal Vectors problem, where given k families A1,…,Ak of subsets of \1,…,d\, each of size n, the task is to find elements ai ∈ Ai for every i ∈ \1,…,k\ such that a1 ∩ a2 ∩ … ∩ ak = ∅. We show that for every fixed k ≥ 2, there exists εk > 0 such that the k-OV problem can be solved in time O(2(1 - εk)⋅ d⋅ n). We also show that, asymptotically, this is the best we can hope for: for any ε > 0 there exists a k ≥ 2 such that 2(1 - ε)⋅ d ⋅ nO(1) time algorithm for k-Orthogonal Vectors would contradict the Set Cover Conjecture.