Finding orthogonal vectors in discrete structures
Finding orthogonal vectors in discrete structures
复制标题
在离散结构中查找正交向量
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Huacheng Yu
中科院分区：
文献类型：
--
作者：
Ryan Williams;Huacheng Yu
d维Hopcroft的问题是给定n个点和n个超平面在Rd上，是否有任何点在任何超平面上？同样地，如果我们有两个集合，每个集合有n个向量，在Rd+1中，是否有一对向量（每个集合中有一个）是正交的？这个问题有着悠久的历史和众多的应用。人们普遍认为，对于较大的d，问题受到维度的诅咒：所有已知的算法对于快速增长的函数f至少需要f(d)·n2-1/O(d)时间，目前几乎没有希望找到n2-e·poly(d)时间算法。
Hopcroft's problem in d dimensions asks: given n points and n hyperplanes in Rd, does any point lie on any hyperplane? Equivalently, if we are given two sets of n vectors each in Rd+1, is there a pair of vectors (one from each set) that are orthogonal? This problem has a long history and a multitude of applications. It is widely believed that for large d, the problem is subject to the curse of dimensionality: all known algorithms need at least f(d) · n2-1/O(d) time for fast-growing functions f, and at the present time there is little hope that a n2-e · poly(d) time algorithm will be found.
We consider Hopcroft's problem over finite fields and integers modulo composites, leading to both surprising algorithms and hardness reductions. The algorithms arise from studying the communication problem of determining whether two lists of vectors (one list held by Alice, one by Bob) contain an orthogonal pair of vectors over a discrete structure (one from each list). We show the randomized communication complexity of the problem is closely related to the sizes of matching vector families, which have been studied in the design of locally decodable codes. Letting HOPCROFTR denote Hopcroft's problem over a ring R, we give randomized algorithms and almost matching lower bounds (modulo a breakthrough in SAT algorithms) for HOPCROFTR, when R is the ring of integers modulo m or a finite field.
Building on the ideas developed here, we give a very simple and efficient output-sensitive algorithm for matrix multiplication that works over any field.