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 |