Write-ups from weekly meeting.

Vaccination game, non-monotonicity example
Logical key tree
Vector packing

Multicut problem: multicut, k-multicut, multiway cut

A survey on Multicut problem and its variants
A survey on Epidemic problems

Feige and Krauthgamer published a paper on Bisection Problem in 2000, which gives a combinatorial algorithm with polylogarithmic approximation ratio. The algorithm contains lots of technical pieces, and is hard to keep all of them in mind or understand the intuition behind them. I wrote a sketch, trying to give a high level structure of the algorithm and some intuition. (In 2008, Racke improved the approximation ratio to O(log n) as a result of his Racke decomposition)

Original paper
My sketch

Some lecture notes I wrote.

Primes is in P
Undirected graph reachability problem
Nash equilibrium and its proof using Fix Point Theorems
Multicommodity flow and Sparsest cut 1
Multicommodity flow and Sparsest cut 2