2026-08-17T18:50:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24564 2025-12-16T14:00:53Z ddc:004 open_access

The Planted Orthogonal Vectors Problem Kühnemann, David Polak, Adam Rosen, Alon Average-case complexity fine-grained complexity orthogonal vectors In the k-Orthogonal Vectors (k-OV) problem we are given k sets, each containing n binary vectors of dimension d = n^o(1), and our goal is to pick one vector from each set so that at each coordinate at least one vector has a zero. It is a central problem in fine-grained complexity, conjectured to require n^{k-o(1)} time in the worst case. We propose a way to plant a solution among vectors with i.i.d. p-biased entries, for appropriately chosen p, so that the planted solution is the unique one. Our conjecture is that the resulting k-OV instances still require time n^{k-o(1)} to solve, on average. Our planted distribution has the property that any subset of strictly less than k vectors has the same marginal distribution as in the model distribution, consisting of i.i.d. p-biased random vectors. We use this property to give average-case search-to-decision reductions for k-OV. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Kühnemann and Adam Polak and Alon Rosen 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.95 urn:nbn:de:0030-drops-245640 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.95 eng https://creativecommons.org/licenses/by/4.0/legalcode