Peanut-Tang

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

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

[GMRZ11] Pseudorandom Generators for Combinatorial Shapes，阅读笔记。该篇论文给出了种子长度为 $O(\log m + \log n + \log^2 (1 / \varepsilon))$ 的 $(m, n)$-Combinatorial Shape 的 $\varepsilon$-PRG。

[Day60] Distribution of Bordered Persymmetric Matrices in a Finite Field，阅读笔记。该篇论文解决了秩为 k 的 Toeplitz 矩阵的计数问题。

这篇博文记录了 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.

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