U.S.-France Cooperative Research: Randomness, Approximation and New Models of Computation

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

9981755 Randall This three-year award for U.S.-France cooperative research in computation and computer research involves Dana Randall, Vijay Vazirani, Leonard Schulman and other researchers from the College of Computing at Georgia Institute of Technology, and Claire Kenyon and the research group at LRI (Laboratoire de Recherche en Informatique), University of Paris, Sud. The project is supported under a joint program of the National Science Foundation and the French National Center for Scientific Research. The project focuses on four areas of research in theoretical computer science, emphasizing applications for approximation algorithms and new models of computation. The areas are: (1) Markov chain Monte Carlo methods for analysis of physical systems; (2) approximation algorithms; (3) codes and loss-resilience in the context of constructing codes for loss information retrieval; and (3) quantum computation, in particular, quantum cryptography. This award will support the incremental costs of the international collaboration; that is, the travel to Paris, France and subsistence expenses of the U.S. investigators. The project takes advantage of complementary expertise of the U.S. and French groups and their work on similar problems. The project will advance fundamental understanding of randomness and approximation problems in computing that are connected to other fields of science, namely, statistical mechanics, data mining, coding theory, and quantum mechanics.