随机算法 (Fall 2011): Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
Line 62: Line 62:
#* [[随机算法 (Fall 2011)/Path Coupling|Path Coupling]]
#* [[随机算法 (Fall 2011)/Path Coupling|Path Coupling]]
#* [[随机算法 (Fall 2011)/Graph Coloring|Graph Coloring]]
#* [[随机算法 (Fall 2011)/Graph Coloring|Graph Coloring]]
# Expander Graphs
# Expander Graphs I
#* [[随机算法 (Fall 2011)/Expander Graphs|Expander Graphs]]
#* [[随机算法 (Fall 2011)/Expander Graphs|Expander Graphs]]
#* [[随机算法 (Fall 2011)/Graph Spectrum|Graph Spectrum]]
#* [[随机算法 (Fall 2011)/Graph Spectrum|Graph Spectrum]]
#* [[随机算法 (Fall 2011)/Random Walk on Expander Graph|Random Walk on Expander Graph]]
# Expander Graphs II
#* [[随机算法 (Fall 2011)/Expander Mixing Lemma|Expander Mixing Lemma]]
#* [[随机算法 (Fall 2011)/Expander Mixing Lemma|Expander Mixing Lemma]]
#* [[随机算法 (Fall 2011)/Random Walk on Expander Graph|Random Walk on Expander Graph]]
#* [[随机算法 (Fall 2011)/Chernoff Bound for Expander Walks|Chernoff Bound for Expander Walks]]
#* [[随机算法 (Fall 2011)/Chernoff Bound for Expander Walks|Chernoff Bound for Expander Walks]]
#* [[随机算法 (Fall 2011)/The Zig-Zag Product|The Zig-Zag Product]]
#* [[随机算法 (Fall 2011)/USTCON in LOGSPACE|USTCON in LOGSPACE]]
# Sampling and Counting
# Sampling and Counting
# MCMC
# MCMC

Revision as of 15:20, 19 July 2011

Lecture Notes

  1. Introduction
  2. Probability Basics
  3. Balls and Bins
  4. Moment and Deviation
  5. Hashing and Fingerprinting
  6. Chernoff Bound
  7. Concentration of Measure
  8. Dimension Reduction
  9. The Probabilistic Method
  10. Approximation Algorithms
  11. Markov Chain and Random Walk
  12. Random Walk Algorithms
  13. Coupling and Mixing Time
  14. Expander Graphs I
  15. Expander Graphs II
  16. Sampling and Counting
  17. MCMC
  18. On-line Algorithms
  19. Complexity
  1. Rapid mixing random walks
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)&oldid=4453"