Orthogonal Vectors
The k-Orthogonal Vectors problem and its planted variants, central to fine-grained complexity and its cryptographic applications.
| Status | Statement | 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