Home Notes Research Fun Stuffs

Fragments

Approximate Counting & Sampling

• Markov chain toolbox
• Lower bounding the mixing times
• Introduction to CFTP
• A CFTP sampler for proper colourings
• Barvinok’s method

Discrete Probability

• Total variation distance
• Lovász local lemma: from probabilistic to constructive
• Precision sampling lemma

Data Structure and Algorithms

• KMP string matching
• String suffixes
• Fast Fourier Transform
• SMAWK minimum search in monotone matrices
• The union-find structure

Graphs

• Cographs

Cryptography

• Public key encryption schemes