高级算法 (Fall 2023)/Problem Set 1

• 作业目前正在更新中，不是最终版

• 每道题目的解答都要有完整的解题过程，中英文不限。

• 我们推荐大家使用LaTeX, markdown等对作业进行排版。

Problem 1 (Min-cut/Max-cut)

• [counting [math]\displaystyle{ \alpha }[/math]-approximate min-cut]
• [weighted min-cut problem]
• [max directed-cut]

Problem 2 (Fingerprinting)

• [Polynomial Identity Testing]
• [Test isomorphism of rooted tree]
• [2D pattern matching]

Problem 3 (Hashing)

• [Bloom filter]
• [Count Distinct Element]

Problem 4 (Concentration of measure)

• [[math]\displaystyle{ k }[/math]-th moment bound]
• [the median trick]
• [cut size in random graph]
• [code rate of boolean code]
• [balls into bins with the "power of two choices"]

Problem 5 (Dimension reduction)

• [inner product]
• [linear separability]
• [sparse vector]

Problem 1 (Lovász Local Lemma)

• [colorable hypergrap]
• [directed cycle]
• [algorithmic LLL]