Faster algorithms for k-Orthogonal Vectors in low dimension

Prelegent(ci)

Anita Dürr

Afiliacja

Saarland University and Max Planck Institute for Informatics

Język referatu

angielski

Termin

17 października 2025 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

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

---