Geometric Tools for Algorithms.
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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.
- Operations Research