Lower Bounds for Linear Degeneracy Testing

Опубликовано 6 сентября 2016, 5:40

Consider the following fundamental problem, called r-linear-degeneracy-testing (rLDT): Given an input of n real numbers, do any r of them sum up to 0? This problem is fundamental in computational geometry as it captures a broad notion of degeneracy, that is, input that satisfies a measure-zero property (not being  in “general position”).  The case r=3 (a.k.a. 3-SUM) is well known and many important computational geometric problems reduce to it.  Its exact complexity is not known and considered a notorious open problem. The talk will discuss lower bounds for rLDT under the linear decision tree model of computation, a natural geometric model which allows the algorithm to compare the input against hyperplanes in n dimensional space.  Erickson proved that under a restricted version of this model, there is a tight bound of n^{r/2}.  I will describe Erickson’s important result and show how to extend it to a more general model of computation.  This generalization, though modest, posed a challenge for many years and demanded new techniques.  The solution I will present gives rise to interesting new problems in linear algebra and combinatorics and strengthens the bold connection between error correcting codes and complexity.  I will describe the new techniques that we developed, their limits, and interesting open problems that may help in further understanding the complexity of this fundamental problem. The talk will be self-contained and no prior background in computational geometry is required, just basic notions of linear algebra. This is joint work with my advisor Bernard Chazelle.