DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2025.95

The Planted Orthogonal Vectors Problem

Authors: David Kühnemann, Adam Polak, and Alon Rosen

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

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.

Cite as

David Kühnemann, Adam Polak, and Alon Rosen. The Planted Orthogonal Vectors Problem. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 95:1-95:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kuhnemann_et_al:LIPIcs.ESA.2025.95,
  author =	{K\"{u}hnemann, David and Polak, Adam and Rosen, Alon},
  title =	{{The Planted Orthogonal Vectors Problem}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{95:1--95:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.95},
  URN =		{urn:nbn:de:0030-drops-245640},
  doi =		{10.4230/LIPIcs.ESA.2025.95},
  annote =	{Keywords: Average-case complexity, fine-grained complexity, orthogonal vectors}
}

Search Results

Documents authored by Kühnemann, David

The Planted Orthogonal Vectors Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message