An Equivalence Class for Orthogonal Vectors
The Orthogonal Vectors problem (OV) asks: given n vectors in {0, 1}O(log n), are two of them orthogonal? OV is easily solved in O(n2 log n) time, and it is a central problem in fine-grained complexity: dozens of conditional lower bounds are based on the popular hypothesis that OV cannot be solved in...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Book |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2021
|
| Online Access: | https://hdl.handle.net/1721.1/130333 |
| _version_ | 1811077085406429184 |
|---|---|
| author | Chen, Lijie Williams, Richard Ryan |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Chen, Lijie Williams, Richard Ryan |
| author_sort | Chen, Lijie |
| collection | MIT |
| description | The Orthogonal Vectors problem (OV) asks: given n vectors in {0, 1}O(log n), are two of them orthogonal? OV is easily solved in O(n2 log n) time, and it is a central problem in fine-grained complexity: dozens of conditional lower bounds are based on the popular hypothesis that OV cannot be solved in (say) n1.99 time. However, unlike the APSP problem, few other problems are known to be non-trivially equivalent to OV. We show OV is truly-subquadratic equivalent to several fundamental problems, all of which (a priori) look harder than OV. A partial list is given below: 1. (Min-IP/Max-IP) Find a red-blue pair of vectors with minimum (respectively, maximum) inner product, among n vectors in {0, 1}O(log n) . 2. (Exact-IP) Find a red-blue pair of vectors with inner product equal to a given target integer, among n vectors in {0, 1}O(log n) . 3. (Apx-Min-IP/Apx-Max-IP) Find a red-blue pair of vectors that is a 100-approximation to the minimum (resp. maximum) inner product, among n vectors in {0, 1}O(log n) . 4. (Approximate Bichrom.-`p-Closest-Pair) Compute a (1+ Ω(1))-approximation to the `p-closest red-blue pair (for a constant p ∈ [1, 2]), among n points in Rd, d ≤ no(1). 5. (Approximate `p-Furthest-Pair) Compute a (1 + Ω(1))approximation to the `p-furthest pair (for a constant p ∈ [1, 2]), among n points in Rd, d ≤ no(1). Therefore, quick constant-factor approximations to maximum inner product imply quick exact solutions to maximum inner product, in the O(log n)-dimensional setting. Another consequence is that the ability to find vectors with zero inner product suffices for finding vectors with maximum inner product. Our equivalence results are robust enough that they continue to hold in the data structure setting. In particular, we show that there is a poly(n) space, n1−ε query time data structure for Partial Match with vectors from {0, 1}O(log n) if and only if such a data structure exists for 1 + Ω(1) Approximate Nearest Neighbor Search in Euclidean space. To establish the equivalences, we introduce two general frameworks for reductions to OV: one based on Σ2 communication protocols, and another based on locality-sensitive hashing families. In addition, we obtain an n2−1/O(log c) time algorithm for Apx-Min-IP with n vectors from {0, 1}c log n, matching state-of-the-art algorithms for OV and Apx-Max-IP. As an application, we obtain a faster algorithm for approximating “almost solvable” MAX-SAT instances. |
| first_indexed | 2024-09-23T10:37:21Z |
| format | Book |
| id | mit-1721.1/130333 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:37:21Z |
| publishDate | 2021 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/1303332022-09-27T10:07:39Z An Equivalence Class for Orthogonal Vectors Chen, Lijie Williams, Richard Ryan Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science The Orthogonal Vectors problem (OV) asks: given n vectors in {0, 1}O(log n), are two of them orthogonal? OV is easily solved in O(n2 log n) time, and it is a central problem in fine-grained complexity: dozens of conditional lower bounds are based on the popular hypothesis that OV cannot be solved in (say) n1.99 time. However, unlike the APSP problem, few other problems are known to be non-trivially equivalent to OV. We show OV is truly-subquadratic equivalent to several fundamental problems, all of which (a priori) look harder than OV. A partial list is given below: 1. (Min-IP/Max-IP) Find a red-blue pair of vectors with minimum (respectively, maximum) inner product, among n vectors in {0, 1}O(log n) . 2. (Exact-IP) Find a red-blue pair of vectors with inner product equal to a given target integer, among n vectors in {0, 1}O(log n) . 3. (Apx-Min-IP/Apx-Max-IP) Find a red-blue pair of vectors that is a 100-approximation to the minimum (resp. maximum) inner product, among n vectors in {0, 1}O(log n) . 4. (Approximate Bichrom.-`p-Closest-Pair) Compute a (1+ Ω(1))-approximation to the `p-closest red-blue pair (for a constant p ∈ [1, 2]), among n points in Rd, d ≤ no(1). 5. (Approximate `p-Furthest-Pair) Compute a (1 + Ω(1))approximation to the `p-furthest pair (for a constant p ∈ [1, 2]), among n points in Rd, d ≤ no(1). Therefore, quick constant-factor approximations to maximum inner product imply quick exact solutions to maximum inner product, in the O(log n)-dimensional setting. Another consequence is that the ability to find vectors with zero inner product suffices for finding vectors with maximum inner product. Our equivalence results are robust enough that they continue to hold in the data structure setting. In particular, we show that there is a poly(n) space, n1−ε query time data structure for Partial Match with vectors from {0, 1}O(log n) if and only if such a data structure exists for 1 + Ω(1) Approximate Nearest Neighbor Search in Euclidean space. To establish the equivalences, we introduce two general frameworks for reductions to OV: one based on Σ2 communication protocols, and another based on locality-sensitive hashing families. In addition, we obtain an n2−1/O(log c) time algorithm for Apx-Min-IP with n vectors from {0, 1}c log n, matching state-of-the-art algorithms for OV and Apx-Max-IP. As an application, we obtain a faster algorithm for approximating “almost solvable” MAX-SAT instances. NSF (Grant CCF-1552651) 2021-04-01T15:25:29Z 2021-04-01T15:25:29Z 2019-01 2021-03-29T16:22:57Z Book http://purl.org/eprint/type/ConferencePaper 9781611975482 https://hdl.handle.net/1721.1/130333 Chen, Lijie and Ryan Williams. "An Equivalence Class for Orthogonal Vectors." Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, January 2019, San Diego, California, Society for Industrial and Applied Mathematics, 2019. © 2019 SIAM en http://dx.doi.org/10.1137/1.9781611975482.2 Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Chen, Lijie Williams, Richard Ryan An Equivalence Class for Orthogonal Vectors |
| title | An Equivalence Class for Orthogonal Vectors |
| title_full | An Equivalence Class for Orthogonal Vectors |
| title_fullStr | An Equivalence Class for Orthogonal Vectors |
| title_full_unstemmed | An Equivalence Class for Orthogonal Vectors |
| title_short | An Equivalence Class for Orthogonal Vectors |
| title_sort | equivalence class for orthogonal vectors |
| url | https://hdl.handle.net/1721.1/130333 |
| work_keys_str_mv | AT chenlijie anequivalenceclassfororthogonalvectors AT williamsrichardryan anequivalenceclassfororthogonalvectors AT chenlijie equivalenceclassfororthogonalvectors AT williamsrichardryan equivalenceclassfororthogonalvectors |