KTH Exchange 6

雖然 course 名是 communication complexity, 但是又會涉及其它 topic

例如昨天就講了經典的 Bipartite Testing
其精彩之處在於證明 G ε-far from bipartite → G_S detects it with high probability, S = random subset of vertex with size O~(1/ε)

愈來愈有味道了!