标题： 植入正交向量问题 显示英文标题

标题： The Planted Orthogonal Vectors Problem

摘要： 在$k$-正交向量（$k$-OV）问题中，我们给定$k$个集合，每个集合包含$n$个维度为$d=n^{o(1)}$的二进制向量，我们的目标是从每个集合中选择一个向量，使得在每个坐标上至少有一个向量具有零。 这是细粒度复杂性中的一个核心问题，据推测在最坏情况下需要$n^{k-o(1)}$时间。 我们提出了一种在具有独立同分布的向量中\emph{植物}解决方案的方法。 $p$偏差条目，对于适当选择的$p$，使得植入的解是唯一的。 我们的猜想是，得到的$k$-OV 实例仍然需要时间$n^{k-o(1)}$来求解，\emph{平均而言}。 我们植入的分布具有这样的性质，任何严格少于$k$个向量的子集都具有\emph{相同}边际分布，如模型分布中的一样，由独立同分布组成。 $p$-偏差随机向量。 我们利用这一性质来为$k$-OV 提供平均情况下的搜索到决策约简。 显示英文摘要

摘要： 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 \emph{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, \emph{on average}. Our planted distribution has the property that any subset of strictly less than $k$ vectors has the \emph{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.