Browsing by Author Ailon, Nir

Jump to: 0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
or enter first few letters:  
Showing results [1 - 1] / 1
  • Authors: Ailon, Nir (2006)

    This work is comprised of three separate parts: (1) Lower bounds for linear degeneracy testing (based on joint work with Bernard Chazelle [5]); (2) Aggregating inconsistent information (based on joint work with Moses Charikar and Alantha Newman [3]); and (3) The fast Johnson-Lindenstrauss transform and approximate nearest neighbor searching (based on joint work with Bernard Chazelle [6]). The first part discusses a fundamental computational geometric problem called rSUM: given n real numbers, do any r of them sum up to 0? It is the simplest case of a more general family of problems called degeneracy testing. This seemingly naive problem is in the core of the di cult y in designing al...