Award Abstract # 0910584
AF: Large: Collaborative Research: Random Processes and Randomized Algorithms

NSF Org: CCF
Division of Computing and Communication Foundations
Recipient: GEORGIA TECH RESEARCH CORP
Initial Amendment Date: September 5, 2009
Latest Amendment Date: September 5, 2009
Award Number: 0910584
Award Instrument: Standard Grant
Program Manager: Balasubramanian Kalyanasundaram
CCF
 Division of Computing and Communication Foundations
CSE
 Directorate for Computer and Information Science and Engineering
Start Date: September 1, 2009
End Date: August 31, 2012 (Estimated)
Total Intended Award Amount: $780,000.00
Total Awarded Amount to Date: $780,000.00
Funds Obligated to Date: FY 2009 = $780,000.00
History of Investigator:
  • Santosh Vempala (Principal Investigator)
    vempala@cc.gatech.edu
  • Dana Randall (Co-Principal Investigator)
  • Prasad Tetali (Co-Principal Investigator)
  • Eric Vigoda (Co-Principal Investigator)
Recipient Sponsored Research Office: Georgia Tech Research Corporation
926 DALNEY ST NW
ATLANTA
GA  US  30318-6395
(404)894-4819
Sponsor Congressional District: 05
Primary Place of Performance: Georgia Institute of Technology
225 NORTH AVE NW
ATLANTA
GA  US  30332-0002
Primary Place of Performance
Congressional District:
05
Unique Entity Identifier (UEI): EMW9FC8J3HN4
Parent UEI: EMW9FC8J3HN4
NSF Program(s): Information Technology Researc,
ALGORITHMS
Primary Program Source: 01000910DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s): 9218, HPCC
Program Element Code(s): 164000, 792600
Award Agency Code: 4900
Fund Agency Code: 4900
Assistance Listing Number(s): 47.070

ABSTRACT

Randomness has emerged as a core concept and tool in computation. From modeling phenomena to efficient algorithms to proof techniques, the applications of randomness are ubiquitous and powerful. Notable examples include: construction of important combinatorial objects such as expanders, rigorously establishing phase transitions in physical models, finding polynomial-time algorithms for fundamental sampling problems and approximating #P-hard counting problems, designing probabilistically checkable proofs (PCP's) and establishing the hardness of approximation, and discovering simpler and often faster algorithms for a variety of computational problems. In the course of these tremendous developments, several general-purpose techniques have emerged, and random sampling has become a fundamental, universal tool across sciences, engineering and computation.

This project brings together leading researchers in randomized algorithms to solve hard problems in random sampling, to identify techniques, and to develop new analytical tools. The applications come from a range of fields, including complexity, physics, biology, operations research and mathematics. The most general and widely-studied technique for sampling is simulating a Markov chain by taking a random walk on a suitable state space. The Markov Chain method and its application to sampling, counting and integration, broadly known as the Markov Chain Monte Carlo (MCMC) method, is a central theme of the project.

Intellectual Merit. The project focuses on applications of randomized algorithms and random sampling to rigorously address problems across several disciplines. Within computer science these topics include: massive data sets, where sampling is critical both for finding low-dimensional representations and clustering; routing networks, where sampling has many applications from monitoring and path allocation to optimization; machine learning; and property testing. Recent interactions between computer science and other scientic disciplines have led to many new rigorous applications of sampling, as well as new insights in how to design and analyze efficient algorithms with performance guarantees; for instance, phase transitions in the underlying physical models can cause local Markov chains to be inefficient. The project explores deeper connections between physics and random sampling, including conjectured correlations between reconstruction problems and thresholds for the efficiency of local algorithms. Many related problems arise in biology, such as phylogenetic tree reconstruction and analysis of complex biological networks. In nanotechology, models of self-assembly are simple Markov chains. In mathematics, the techniques used in the analysis of sampling algorithms in general and Markov chains in particular have drawn heavily on probability theory, both discrete and continuous.

Broader Impact. The college of computing at Georgia Tech is home to the new Algorithms and Randomness Center (ARC) with many faculty and students sharing this expertise. The project's activities include designing a summer school for graduate students in randomized algorithms and designing a course for training students from diverse backgrounds and hosting workshops focusing on both theoretical and applied aspects of randomized algorithms. Participation of women and under-represented groups in all of these activities will be encouraged, and the workshops will include tutorials to increase accessibility. These coordinated efforts in education and research will solidify the impact of ARC and make it a premier center for algorithms, randomness and complexity.

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Note:  When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

(Showing: 1 - 10 of 34)
[10] D. Stefankovic and E. Vigoda "Fast Convergence of MCMC Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species" SIAM Journal on Discrete Mathematics , 2011
[11] D. Stefankovic, S. Vempala, and E. Vigoda "A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions" SIAM Journal on Computing , v.41 , 2012 , p.356
[12] N. Bhatnagar, J. Vera, E. Vigoda, and D. Weitz "Reconstruction for Colorings on Trees" SIAM Journal of Discrete Mathematics , 2011
[13] S. Greenberg and D. Randall "Convergence Rates of Markov Chains for Some Self-Assembly and Non-Saturated Ising Models" Theoretical Computer Science , v.410 , 2009 , p.1417
[14] M. Cryan, M. Dyer and D. Randall "Approximately Counting Integer Flows and Cell-Bounded Contingency Tables" SIAM Journal on Computing , 2010
[14] M. Cryan, M. Dyer and D. Randall "Approximately Counting Integer Flows and Cell-Bounded Contingency Tables" SIAM Journal on Computing , v.39 , 2010 , p.2683
[15] I. Bez\'{a}kov\'{a}, N. Bhatnagar and D. Randall. "On the Diaconis-Gangolli Markov Chain for sampling contingency tables with cell-bounded entries" 15th International Computing and Combinatorics Conference (COCOON) , 2009
[15] I. Bez\'{a}kov\'{a}, N. Bhatnagar and D. Randall. "On the Diaconis-Gangolli Markov Chain for sampling contingency tables with cell-bounded entries" J. Combinatorial Optimization and 15th International Computing and Combinatorics Conference (COCOON) , v.22 , 2011 , p.4
[16] K. Chandrasekaran, D. Dadush and S. Vempala "Thin Partitions: Sampling and Isoperimetry for Star-shaped Bodies" ACM-SIAM SODA , 2010
[17] K. Chandrasekaran, B. Haeupler and N. Goyal "Deterministic Algorithms for the Lovasz Local Lemma" ACM-SIAM SODA , 2010
[18] M. Barasz and S. Vempala "A new approach to strongly polynomial Linear Programming" Innovations in Computer Science , 2010
(Showing: 1 - 10 of 34)

Please report errors in award information by writing to: awardsearch@nsf.gov.

Print this page

Back to Top of page