Kさんからスライドを頂いて，楽をしている．

Adrian Dumitrescu http://arxiv.org/abs/1004.1654幾何学的なRamsey理論はまだまだ未発達で未解決問題も多い，という状況はGrahamの書いた「Handbook of Discrete and Computational Geometry」の賞を見ても分かる．グリッドに対する幾何学的Ramsey理論は数…

Anna Blasiak, Robert Kleinberg, Eyal Lubetzky http://arxiv.org/abs/1004.1379長くて読む気がなかなか湧かないけど．符号の問題．送り手はn個のメッセージx1からxnまでを持っていて，n人いる受け手はそれぞれxiを受け取りたい．そのとき，受け手は自分が…

Anastasios Sidiropoulos http://arxiv.org/abs/1004.1666種数gのグラフを平面的グラフ (種数0のグラフ) に埋め込むときに歪みをできるだけ小さくしたいという話があり，最適な歪みO(log g)を達成する埋め込みを多項式時間で見つけることができるようになり…

Ravindran Kannan http://arxiv.org/abs/1004.1253今度のSTOCでRavi Kannanが行うチュートリアル講演の内容．スペクトル法についてのサーベイ．知識発見とかクラスタリングとかやってる人には重要だと思う．

今週の壊滅的ダメージから立ち直るために，次回はかなり慎重になりそうな予感．

Pavol Hell, Arash Rafiey http://arxiv.org/abs/1004.2908これはまた別のdichotomy．本当に多い．

Jin-Yi Cai, Sangxia Huang, Pinyan Lu http://arxiv.org/abs/1004.0803最近dichotomy定理がどんどん出てきて，全く追えなくなってるので，もう一度ちゃんと復習しないといけないなと思っていても，どんどん出てくるという状況なのは，おそらく研究がかなり…

Matt Gibson, Imran A. Pirwani http://arxiv.org/abs/1004.3320平面上のdiskのintersectionグラフにおける最小支配集合問題がPTASを持つかどうかは大きな未解決問題であったが，この論文はそれを肯定的に解決している．去年のSoCGでChan & Har-PeledとMusta…

Rahul Jain, Hartmut Klauck, Miklos Santha http://arxiv.org/abs/1004.0105上の「Constructive Proofs of Concentration Bounds」とも若干関係するが，optimal direct sum theoremというものが様々な計算モデルについて知られているようで，この論文ではそ…

Russell Impagliazzo, Valentine Kabanets http://eccc.hpi-web.de/report/2010/072/さて，離散数学における確率論的手法の分野において「constructive proof」が最近注目されている気がする．その端緒はMoserによるLovasz Local Lemmaのconstructive proof …

Klaus Dohmen http://arxiv.org/abs/1004.3416Chordalグラフのクリークの族に対して，Bonferroniの不等式のようなものが成り立つ，ということを言っている．いわゆる包除原理は球体 (ball) のcontractibilityと同じことをいってるようなものなので，chordal…