Finding orthogonal vectors in discrete structures

Hopcroft's problem in d dimensions asks: given n points and n hyperplanes in R^d, does any point lie on any hyperplane? Equivalently, if we are given two sets of n vectors each in R^d+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) · n^2-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 HOPCROFT_R denote Hopcroft's problem over a ring R, we give randomized algorithms and almost matching lower bounds (modulo a breakthrough in SAT algorithms) for HOPCROFT_R, 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.