Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916460018794496 |
|---|---|
| author | Alman, Josh Andoni, Alexandr Zhang, Hengjie |
| author_facet | Alman, Josh Andoni, Alexandr Zhang, Hengjie |
| contents | We study the average-case version of the Orthogonal Vectors problem, in which one is given as input $n$ vectors from $\{0,1\}^d$ which are chosen randomly so that each coordinate is $1$ independently with probability $p$. Kane and Williams [ITCS 2019] showed how to solve this problem in time $O(n^{2 - δ_p})$ for a constant $δ_p > 0$ that depends only on $p$. However, it was previously unclear how to solve the problem faster in the hardest parameter regime where $p$ may depend on $d$.
The best prior algorithm was the best worst-case algorithm by Abboud, Williams and Yu [SODA 2014], which in dimension $d = c \cdot \log n$, solves the problem in time $n^{2 - Ω(1/\log c)}$. In this paper, we give a new algorithm which improves this to $n^{2 - Ω(\log\log c /\log c)}$ in the average case for any parameter $p$.
As in the prior work, our algorithm uses the polynomial method. We make use of a very simple polynomial over the reals, and use a new method to analyze its performance based on computing how its value degrades as the input vectors get farther from orthogonal.
To demonstrate the generality of our approach, we also solve the average-case version of the closest pair problem in the same running time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_22477 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems Alman, Josh Andoni, Alexandr Zhang, Hengjie Data Structures and Algorithms We study the average-case version of the Orthogonal Vectors problem, in which one is given as input $n$ vectors from $\{0,1\}^d$ which are chosen randomly so that each coordinate is $1$ independently with probability $p$. Kane and Williams [ITCS 2019] showed how to solve this problem in time $O(n^{2 - δ_p})$ for a constant $δ_p > 0$ that depends only on $p$. However, it was previously unclear how to solve the problem faster in the hardest parameter regime where $p$ may depend on $d$. The best prior algorithm was the best worst-case algorithm by Abboud, Williams and Yu [SODA 2014], which in dimension $d = c \cdot \log n$, solves the problem in time $n^{2 - Ω(1/\log c)}$. In this paper, we give a new algorithm which improves this to $n^{2 - Ω(\log\log c /\log c)}$ in the average case for any parameter $p$. As in the prior work, our algorithm uses the polynomial method. We make use of a very simple polynomial over the reals, and use a new method to analyze its performance based on computing how its value degrades as the input vectors get farther from orthogonal. To demonstrate the generality of our approach, we also solve the average-case version of the closest pair problem in the same running time. |
| title | Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.22477 |