Sem 4 之後: 516 Project

由於去 world final 的關係, 逼不得而把 516 project 的 deadline 延後數日
topic 是 Graph Sparsifiers
一開始會選這個 topic 是覺得個 result 很強勁很神奇, 大約就是說
Given 一個任意的 weighted graph G, 可以 produce 一個 O(n/ε²) 條 edge 的 graph H, 而 H 是 G 的 ε-approximation

由於時間關係, 基本上只看了一篇 paper
一開始被整頁的運算, 公式嚇到
不過後來發現那些運算大多都是移項, 加加減減
真正難的地方在於對整個 proof 流程的理解
閉關了數個下午總算大致明白

做完後的感覺:
首先覺得個 proof 很神奇, 很多步都很有出 cheat 的感覺
對 linear algebra 又熟了一點
「知道 result」和「知道 proof」的分別就像睇戲和睇 behind the scene