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 Structures & Algorithms

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

Graphs

• Cographs

Geometry

• How Long Is the Daytime Today?

Complexity & Cryptography

• Complexity of the game Manufactoria
• Public key encryption schemes