{"ID":2894309,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.11098","arxiv_id":"2507.11098","title":"Faster algorithms for k-Orthogonal Vectors in low dimension","abstract":"In the Orthogonal Vectors problem (OV), we are given two families $A, B$ of subsets of $\\{1,\\ldots,d\\}$, each of size $n$, and the task is to decide whether there exists a pair $a \\in A$ and $b \\in B$ such that $a \\cap b = \\emptyset$. Straightforward algorithms for this problem run in $\\mathcal{O}(n^2 \\cdot d)$ or $\\mathcal{O}(2^d \\cdot n)$ time, and assuming SETH, there is no $2^{o(d)}\\cdot n^{2-\\varepsilon}$ time algorithm that solves this problem for any constant $\\varepsilon \u003e 0$. Williams (FOCS 2024) presented a $\\tilde{\\mathcal{O}}(1.35^d \\cdot 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 $\\tilde{\\mathcal{O}}(1.25^d n)$. This can be improved to $\\mathcal{O}(1.16^d \\cdot n)$ using computer-aided evaluations. We generalize our result to the $k$-Orthogonal Vectors problem, where given $k$ families $A_1,\\ldots,A_k$ of subsets of $\\{1,\\ldots,d\\}$, each of size $n$, the task is to find elements $a_i \\in A_i$ for every $i \\in \\{1,\\ldots,k\\}$ such that $a_1 \\cap a_2 \\cap \\ldots \\cap a_k = \\emptyset$. We show that for every fixed $k \\ge 2$, there exists $\\varepsilon_k \u003e 0$ such that the $k$-OV problem can be solved in time $\\mathcal{O}(2^{(1 - \\varepsilon_k)\\cdot d}\\cdot n)$. We also show that, asymptotically, this is the best we can hope for: for any $\\varepsilon \u003e 0$ there exists a $k \\ge 2$ such that $2^{(1 - \\varepsilon)\\cdot d} \\cdot n^{\\mathcal{O}(1)}$ time algorithm for $k$-Orthogonal Vectors would contradict the Set Cover Conjecture.","short_abstract":"In the Orthogonal Vectors problem (OV), we are given two families $A, B$ of subsets of $\\{1,\\ldots,d\\}$, each of size $n$, and the task is to decide whether there exists a pair $a \\in A$ and $b \\in B$ such that $a \\cap b = \\emptyset$. Straightforward algorithms for this problem run in $\\mathcal{O}(n^2 \\cdot d)$ or $\\ma...","url_abs":"https://arxiv.org/abs/2507.11098","url_pdf":"https://arxiv.org/pdf/2507.11098v1","authors":"[\"Anita Dürr\",\"Evangelos Kipouridis\",\"Karol Węgrzycki\"]","published":"2025-07-15T08:45:24Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}