This project is focused on two areas. The first is applying techniques developed for randomized algorithms to traditional matrix problems that have to be solved for very large matrices. In particular, the problem of finding an approximation to a given matrix having a fixed rank. If the matrix is the adjacency matrix of a graph, connection has been developed between such approximations and certain partitions of the vertex set of the graph. The second area is approximation algorithms for convex sets.
