| SES # | READINGS |
|---|---|
| A. Second Moment Method: The second moment method is a simple probabilistic tool to establish existence of non-rare events in a complex setup. | |
| 1 | Frieze, Alan, and Nicholas C. Wormald. "Random k-SAT: A Tight Threshold for Moderately Growing k." Combinatorica 25, no. 3 (2005): 297-305. (PDF) |
| 2 | Achlioptas, Dimitris, and Assaf Naor. "The Two Possible Values of the Chromatic Number of a Random Graph." Annals of Mathematics 162, no. 3 (2005): 1335-1351. (PDF) |
| B. Local Weak Convergence and Correlation Decay: The notion of local weak convergence allows one to study asymptotic spatial structural properties of probabilistic combinatorial optimization problems. The property of correlation decay facilitates one to establish these properties. | |
| 3 | Kelly, F. P. "Stochastic Models of Computer Communication Systems (in A Symposium on Stochastic Networks)." Journal of the Royal Statistical Society. Series B (Methodological) 47, no. 3 (1985): 379-395. |
| 4 | Weitz, D. "Counting Independent Sets up to the Tree Threshold." (PDF) |
| 5 |  Aldous, D., and J. Steele. "The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence." In Probability on Discrete Structures. Edited by Harry Kesten. New York, NY: Springer-Verlag, 2003. ISBN: 3540008454. (PS) |
| 6 | Gamarnik, David, Tomasz Nowicki, and Grzegorz Swirszcz. "Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results Using the Local Weak Convergence Method." Random Structures and Algorithms 28, no. 1 (2006): 76-106. (PDF) |
| C. Belief Propagation and LDPC Codes: Belief propagation is an iterative distributed heuristic algorithm for combinatorial optimization problem. It is expected to perform very well in the context of probabilistic setup. | |
| 7-8 | Wainwright, M. J., and M. I. Jordan. "Graphical Models, Exponential Families and Variational Inference." UC Berkeley, Dept. of Statistics, Technical Report 649 (2003). (PS - 1.7 MB) |
| 9 | Bayati, M., D. Shah, and M. Sharma. "Maximum Weight Matching via Max-product Belief Propagation." International Symposium on Information Theory, Proceedings (2005): 1763-1767. |
| 10 | Richardson, T., and R. Urbanke. Modern Coding Theory. Cambridge, UK: Cambridge University Press, 2006, chapters 1 and 2. (Forthcoming) |
Table of Contents
Study Materials
Readings
| When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more. |
Special software is required to use some of the files in this section: .xls.