Orthogonal Vectors
The k-Orthogonal Vectors problem and its planted variants, central to fine-grained complexity and its cryptographic applications.
| Status | Problem | Tags |
|---|---|---|
|
Planted k-OV Hardness Conjecture 10 of the source, and a newly proposed average-case assumption rather than a question the literature already asked. Its worst-case counterpart – that \(k\)-OV requires \(n^{k-o(1)}\) time – is a central conjecture of fine-grained complexity. The planting preserves the marginal distribution of any subset of fewer than \(k\) vectors, and the source gives a search-to-decision reduction. 5 open |
Average Case HardnessFine Grained CryptographyOrthogonal VectorsPlanted Constraint Satisfactionassumption |
No matching items