Computer Science Department
School of Computer Science, Carnegie Mellon University
Geometric Tools for Algorithms
Keywords: Geometric algorithms, randomization, outliers, sampling,
information retrieval, machine learning
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 half-spaces, (3) clustering text corpora,
and (4) counting lattice points in a convex body.
We supplement some of our theorems with experimental studies.