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):

Report Date:

1997-08-01

Pagination or Media Count:

85.0

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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE