270561



    ABSTRACTS VIEWS

    5024



    VIEWS & DOWNLOAD

    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
    • 3223847.PDF.jpg
    • Thesis


    • 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...