College of Computing Postdoctoral Fellow and ARC ThinkTank member Luis Rademacher has won the Johnson prize for 2006-07, given by the MIT mathematics department to the most outstanding paper co-authored by a graduate student.

Rademacher's paper, titled "Dispersion of Mass and the Complexity of Randomized Geometric Algorithms," deals with computing the volume of a convex body--an ancient mathematical problem studied by Euclid, Kepler and Minkowski, among others. The paper was a collaboration with his advisor, College of Computing Professor and ARC ThinkTank Director Santosh Vempala. The paper appeared last year in the IEEE Symposium on the Foundations of Computer Science.

In his work, Rademacher proves a nearly quadratic lower bound on the complexity of any randomized algorithm that approximates the volume of a convex body in R^n. The lower bound complements progress over the past two decades on efficient algorithms for volume computation. It does so using deep new connections between convex geometric analysis and algorithmic complexity.

Read the paper