TY - GEN

T1 - Finding orthogonal vectors in discrete structures

AU - Williams, Ryan

AU - Yu, Huacheng

PY - 2014

Y1 - 2014

N2 - 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 /, and at the present time there is little hope that a n2~£ • poly(t/) 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.

AB - 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 /, and at the present time there is little hope that a n2~£ • poly(t/) 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.

UR - http://www.scopus.com/inward/record.url?scp=84902106705&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902106705&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973402.135

DO - 10.1137/1.9781611973402.135

M3 - Conference contribution

AN - SCOPUS:84902106705

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1867

EP - 1877

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery

T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

Y2 - 5 January 2014 through 7 January 2014

ER -