This research concerns two areas in geometric algorithms, including the exploration of some promising connections between them. One area is the application of random walk techniques in the design of algorithms for sampling from a convex body, volume computation, and related geometric problems like bringing a convex body to isotropic position. The key technique is using a random walk to generate sample points, and the analysis of mixing and other properties of this walk. Further improvements depend on a number of unresolved technical questions, mostly in geometry but also connected with Markov chains. The other topic is geometric representations of graphs, and the application of such representations in the design of graph algorithms. This has surprising connections with graph properties and parameters like chromatic number, cliques, connectivity, cuts, and topological embeddablity. Representations with favorable properties can be used to design exact or approximation algorithms for many such problems. There are geometric representations connected with random walks on graphs, and geometric properties of these representations reflect mixing properties of the random walk. Applications of these representations in the analysis of random walk techniques are being studied.
