Faster algorithms for k-Orthogonal Vectors in low dimension

Speaker(s)

Anita Dürr

Affiliation

Saarland University and Max Planck Institute for Informatics

Language of the talk

English

Date

Oct. 17, 2025, 2:15 p.m.

Room

room 5060

Seminar

Seminar Algorithms

---

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(n^2 · d) or O(2^d · n) time, and assuming SETH, there is no 2^o(d) · n^(2−ε) time algorithm that solves this problem for any constant ε > 0.
Williams (FOCS 2024) presented a ˜O(1.35^d · 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.25^d · n). This can be improved to O(1.16^d · n) using computer-aided evaluations.

The talk is based on the work: https://arxiv.org/abs/2507.11098

---