Peanut-Tang

每次都要上网搜太麻烦了，故：

搬运自：https://www.luogu.com.cn/blog/IowaBattleship/latex-gong-shi-tai-quan

这篇博文记录了 read-once branching program 三种本质相同的 pseudorandom generator —— [Nisan’92]、[Impagliazzo-Nisan-Wigderson’94] 和 [Nisan-Zuckerman’96]。

分别阐述了三种 PRG 的构造方法，最后用 Leftover Hash Lemma 这一桥梁将三者联系在一起。

非常有趣的一道概率方法题，记录一下。

[ALT21] An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models, reading note.

Auction is an amazing algorithm!

[ER17] On Sampling Edges Almost Uniformly, reading note; also the note of the talk given by Professor Talya Eden in workshop WoLA.

做多校的时候碰见了这个技巧，记录下来。只能说高中的时候没有好好学生成函数，现在回看有些东西其实没有那么难的，应该认真地体系地学一下。

把一些个课程在复习期中期末时自己捋思路的笔记扫描了一下传到博客里。

Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming (Michael X. Coemans and David P. Williamso, 1994) reading note.