Santosh Vempala
Thesis Title:
Geometric Tools for Algorithms
Degree Type:
Ph.D. in Algorithms, Combinatorics and Optimization
Advisor(s):
Avrim Blum
Graduated:
August
1997
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 half-spaces, (3) clustering text corpora, and (4) counting lattice points in a convex body.
We supplement some of our theorems with experimental studies.
Thesis Committee:
Avrim Blum (Chair)
Alan Frieze
Ravi Kannan
László Lovász (Yale University)
James Morris, Head, Computer Science Department
Raj Reddy Dean, School of Computer Science
Keywords: Geometric algorithms, randomization, outliers, sampling, information retrieval, machine learning
CMU-CS-97-167.pdf (451.02 KB) ( 86 pages)Copyright Notice