Thursday, June 07, 2007

Note: Asaf Shapira's talk

Speaker: Asaf Shapira

Noga Alon's Ph.D student
homepage: http://www.math.tau.ac.il/~asafico/


Title: A Charaterization of the Testable Graph Properties
Link: (CLICK HERE)


我所領悟的大意是,許多 Testable graph properties 可以看(轉)成 partition problems,因此跟 Szemerédi's Regularity Lemma 脫不了關係。

另外,很多我所知道的 testers 都是 nonadaptive and oblivious,因為這些 testers 在 query 時不用知道前面 query 的結果(一口氣把所有該 query 的 query 完)而且不用知道 input graph 的 size。

=====================================================

今天看了 (upper/lower) asymptotic density of a set of natural numbers,接下來可以試著把 Szemerédi's theorem 弄得更加清楚。

No comments: