The Orthogonal Vectors Conjecture for Branching Programs and Formulas
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
复制标题
分支程序和公式的正交向量猜想
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Richard Ryan Williams
中科院分区：
文献类型：
--
作者：
D. Kane;Richard Ryan Williams
在正交矢量（OV）问题中，我们希望确定$ n $ boolean矢量之间是否有$ d $ dimensions中的矢量对矢量。 OV猜想（OVC）认为OV需要$ n^{2-o（1）} $时间来求解时间，对于所有$ d = \ omega（\ log n）$。假设OVC在$ p $中的许多突出问题中已证明了最佳时间下限。
我们证明OVC在几种关注的计算模型中是正确的：
*对于所有足够大的$ n $和$ d $，$ n $ vectors in $ \ {0,1 \}^d $具有分支程序复杂性$ \ tilde {\ theta}（n \ cdot \ min（n n）） ，2^d））$。特别是，下限与上限与各个界限匹配。
* OV具有布尔公式复杂性$ \ tilde {\ theta}（n \ cdot \ min \ min（n，2^d））$，在$ o（1）$ fan-in的所有完整基础上。
* ov需要$ \ tilde {\ theta}（n \ cdot \ min（n，2^d））$ dire，该公式包含由门计算的无界风扇中的任意对称函数组成的公式。
我们的下限基本上与这些模型中任何显式功能的最著名（二次）下限匹配。在OVC下显示出许多相关问题的类似下限，例如批处理部分匹配，批处理子集查询和批处理锤最近的邻居，所有这些问题都非常简洁地减少了OV。
证明使用某种类型的输入限制，这与独立分配变量分配的典型随机限制不同。我们给出了一个理解的，即独立的随机限制不能用于显示硬度，因为即使对于$ ac^0 $公式，OVC在“平均情况”中是错误的：
*对于（0,1）$中的每个固定$ p \ in（0,1）$，都有一个$ \ epsilon_p> 0 $，以便对于每个$ n $和$ d $，ov ov instances intupt bits独立设置为$ 1 $，均为$ p p $（和$ 0 $否则）可以用$ ac^0 $ size $ o（n^{2- \ epsilon_p}）$解决，除了一个$ o_n（1）$的实例分数。
In the Orthogonal Vectors (OV) problem, we wish to determine if there is an orthogonal pair of vectors among $n$ Boolean vectors in $d$ dimensions. The OV Conjecture (OVC) posits that OV requires $n^{2-o(1)}$ time to solve, for all $d=\omega(\log n)$. Assuming the OVC, optimal time lower bounds have been proved for many prominent problems in $P$.
We prove that OVC is true in several computational models of interest:
* For all sufficiently large $n$ and $d$, OV for $n$ vectors in $\{0,1\}^d$ has branching program complexity $\tilde{\Theta}(n\cdot \min(n,2^d))$. In particular, the lower bounds match the upper bounds up to polylog factors.
* OV has Boolean formula complexity $\tilde{\Theta}(n\cdot \min(n,2^d))$, over all complete bases of $O(1)$ fan-in.
* OV requires $\tilde{\Theta}(n\cdot \min(n,2^d))$ wires, in formulas comprised of gates computing arbitrary symmetric functions of unbounded fan-in.
Our lower bounds basically match the best known (quadratic) lower bounds for any explicit function in those models. Analogous lower bounds hold for many related problems shown to be hard under OVC, such as Batch Partial Match, Batch Subset Queries, and Batch Hamming Nearest Neighbors, all of which have very succinct reductions to OV.
The proofs use a certain kind of input restriction that is different from typical random restrictions where variables are assigned independently. We give a sense in which independent random restrictions cannot be used to show hardness, in that OVC is false in the "average case" even for $AC^0$ formulas:
* For every fixed $p \in (0,1)$ there is an $\epsilon_p > 0$ such that for every $n$ and $d$, OV instances where input bits are independently set to $1$ with probability $p$ (and $0$ otherwise) can be solved with $AC^0$ formulas of size $O(n^{2-\epsilon_p})$, on all but a $o_n(1)$ fraction of instances.