|
Award Abstract #0237834
CAREER: Markov Chain Monte Carlo Methods
| NSF Org: |
CCF
Division of Computer and Communication Foundations
|
|
|
| Initial Amendment Date: |
May 5, 2003 |
|
| Latest Amendment Date: |
May 27, 2004 |
|
| Award Number: |
0237834 |
|
| Award Instrument: |
Continuing grant |
|
| Program Manager: |
David Hung-Chang Du
CCF Division of Computer and Communication Foundations
CSE Directorate for Computer & Information Science & Engineering
|
|
| Start Date: |
August 1, 2003 |
|
| Expires: |
November 30, 2004 (Estimated) |
|
| Awarded Amount to Date: |
$157228 |
|
| Investigator(s): |
Eric Vigoda vigoda@cc.gatech.edu (Principal Investigator)
|
|
| Sponsor: |
University of Chicago
5801 South Ellis Avenue
Chicago, IL 60637 773/702-8602
|
|
| NSF Program(s): |
THEORY OF COMPUTING
|
|
| Field Application(s): |
|
|
| Program Reference Code(s): |
HPCC,9216,1187,1045
|
|
| Program Element Code(s): |
2860
|
ABSTRACT
Markov chain Monte Carlo (MCMC) methods are an important
algorithmic device in a variety of fields. This project studies
techniques for rigorous analysis of the convergence properties of
Markov chains. The emphasis is on refining probabilistic,
analytic and combinatorial tools (such as coupling, log-Sobolev,
and canonical paths) to improve existing algorithms and develop
efficient algorithms for important open problems.
Problems arising in computer science, discrete mathematics,
and physics are of particular interest, e.g., generating random
colorings and independent sets of bounded-degree graphs,
approximating the permanent, estimating the volume of a
convex body, and sampling contingency tables. The project
also studies inherent connections between phase
transitions in statistical physics models and convergence
properties of associated Markov chains.
The investigator is developing a new graduate course on MCMC methods.
Please report errors in award information by writing to: awardsearch@nsf.gov.
|
