DIMACS: Series in Discrete Mathematics and Theoretical Computer Science 2004; 105 pp; softcover Volume: 65 Reprint/Revision History: reprinted 2005 ISBN10: 0821837931 ISBN13: 9780821837931 List Price: US$43 Member Price: US$34.40 Order Code: DIMACS/65.S
 Random projection is a simple geometric technique for reducing the dimensionality of a set of points in Euclidean space while preserving pairwise distances approximately. The technique plays a key role in several breakthrough developments in the field of algorithms. In other cases, it provides elegant alternative proofs. The book begins with an elementary description of the technique and its basic properties. Then it develops the method in the context of applications, which are divided into three groups. The first group consists of combinatorial optimization problems such as maxcut, graph coloring, minimum multicut, graph bandwidth and VLSI layout. Presented in this context is the theory of Euclidean embeddings of graphs. The next group is machine learning problems, specifically, learning intersections of halfspaces and learning large margin hypotheses. The projection method is further refined for the latter application. The last set consists of problems inspired by information retrieval, namely, nearest neighbor search, geometric clustering and efficient lowrank approximation. Motivated by the first two applications, an extension of random projection to the hypercube is developed here. Throughout the book, random projection is used as a way to understand, simplify and connect progress on these important and seemingly unrelated problems. The book is suitable for graduate students and research mathematicians interested in computational geometry. Copublished with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 17 were copublished with the Association for Computer Machinery (ACM). Readership Graduate students and research mathematicians interested in computational geometry. Reviews "A very nice piece of work  the author succeeds in tying together a lot of recent developments in algorithms under an appealing theme."  Professor Jon Kleinberg, Cornell University "This is an elegant monograph, dense in ideas and techniques, diverse in its applications, and above all, vibrant with the author's enthusiasm for the area."  from the Foreword by Christos H. Papadimitriou, University of California, Berkeley Table of Contents Combinatorial optimization  Rounding via random projection
 Embedding metrics in Euclidean space
 Euclidean embeddings: Beyond distance preservation
Learning theory  Robust concepts
 Intersections of halfspaces
Information retrieval  Nearest neighbors
 Indexing and clustering
 Bibliography
 Appendix
