Accession Number : ADA329831

Title :   Geometric Tools for Algorithms.

Descriptive Note : Doctoral thesis,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Vempala, Santosh

PDF Url : ADA329831

Report Date : AUG 1997

Pagination or Media Count : 85

Abstract : Our thesis is that a geometric perspective yields insights into the structure of fundamental problems, and thereby suggests efficient algorithms for them. As evidence we develop new geometric models and general-purpose tools for removing outliers from numeric data, reducing dimensionality, and counting combinatorial sets. Then we apply these techniques to a set of old problems to obtain polynomial-time algorithms. These include: (1) learning noisy linear-threshold functions (half-spaces), (2) learning the intersection of halfspaces, (3) clustering text corpora, and (4) counting lattice points in a convex body. We supplement some of our theorems with experimental studies.

Descriptors :   *ALGORITHMS, *NUMERICAL ANALYSIS, MODELS, COUNTING METHODS, THESES, SAMPLING, INFORMATION RETRIEVAL, GEOMETRY.

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE