Lecture | Topic | Notes | Reading | Files |

Lecture 1 (03/28/2023) | Introduction, The probabilistic Method, Linearity of Expectations | pdf | Chapters 1,2 of Alon-Spencer Inapproximability of Max 3SAT A 7/8 approximation Alg for Max 3SAT |

Lecture 2 (03/30/2023) | Second Moment Method | pdf | Chapter 3 of Alon-Spencer Kahn-Kalai Conjecture and Phase Transition in Random Graphs |

Lecture 3 (04/04/2023) | Unreliability, DNF Couting | pdf | A recent work on unreliability with improved runtime |

Lecture 4 (04/06/2023) | Strong Concentration Bounds, Routing with minimum Congestion | pdf | Hardness results on Min Congestion Problem |

Lecture 5 (04/11/2023) | Lovasz Local Lemma | pdf | Chapter 5 of the Alon-Spencer Book Local Lemma and Maximizing Fairness |

Lecture 6 (04/13/2023) | Algorithmic Lovasz Local Lemma | pdf | A generalization of Moser-Tardos argument |

Lecture 7 (04/18/2023) | Negative Correlationand Concentration | pdf | Chapter 6 of Alon-Spencer book, Towards a Theory of Negative Dependence |

Lecture 8 (04/20/2023) | Intro to Strongly Rayleigh Distributions | pdf | Negtative Dependence and Geometry of Polynomials Concentration of Lipshitz functions of SR Distributions On Efficient Sampling SR Distributions |

Lecture 9 (04/25/2023) | Martingales I: Azuma's Inequality | pdf | Chapter 7 of Alon-Spencer Book |

Lecture 10 (04/27/2023) | Martingales II: Pipage Rounding | pdf | Swap Rounding and Applications |

Lecture 11 (05/02/2023) | Random Walks and Electrical networks | pdf | |

Lecture 12 (05/04/2023) | Hitting Time and Cover Time | pdf | Random Walks and Effective Resistance Survey Fast Generation of Random Spanning Trees using Eff Resistnce Metric A Deterministic Algorithm to Estimate Covertime |

Lecture 13 (05/09/2023) | Matrix Chernoff Bound | pdf | Matrix Chernoff bound for SR dist Matrix Chernoff bound for Expander Walks |

Lecture 14 (05/11/2023) | Spectral Sparsification of Graphs | pdf | Hypergraph Spectral Sparsification Linear Sized Spectral Sparsifiers Dynamic Spectral Sparsification in Linear Time and Space Effective Resistance Sparsifiers |

Lecture 15 (05/16/2023) | Intro to Markov Chain Mixing Time | pdf | |

Lecture 16 (05/18/2023) | Coupling Method: Counting Coloring | pdf | Riffle SHuffle |

Lecture 17 (05/23/2023) | Copuling Continued | pdf | Improved Bounds for Sampling Colorings Coupling with the Stationary Distribution |

Lecture 18 (05/25/2023) | Bounding Mixing Tie by Poincare Constant | pdf | Counting Perfect Matchings in Bipartite Graphs MCMC for Sampling SR Distributions MCMC for the Ising Model MCMCM for Sampling Bases of Matroids |

Lecture 19 (05/25/2023) | Sampling Matchings in General Graphs | | |