The Chordal Graph Sieve: Lower Bounds

論文紹介

Klaus Dohmen
http://arxiv.org/abs/1004.3416

Chordalグラフのクリークの族に対して，Bonferroniの不等式のようなものが成り立つ，ということを言っている．いわゆる包除原理は球体 (ball) のcontractibilityと同じことをいってるようなものなので，chordalグラフのクリーク複体がcontractibleであるということを知っていれば (これは私が関連する論文を書いたEdelman-Reiner ('00) の結果である)，この論文の結果はさほど驚きではない，と思う．

Constructive Proofs of Concentration Bounds

論文紹介

Russell Impagliazzo, Valentine Kabanets
http://eccc.hpi-web.de/report/2010/072/

さて，離散数学における確率論的手法の分野において「constructive proof」が最近注目されている気がする．その端緒はMoserによるLovasz Local Lemmaのconstructive proof (とそれのMoser & Tardosによる一般化) だと思うけども，この論文はChernoffの不等式のconstructive proofをしていて，その一般化を証明することで様々な帰結を導きだしている．この論文のイントロを読むと，その辺りの話題が離散数学，計算量理論，暗号理論でどのような役割を果たしていて，どういう歴史をたどってきたかということを少しは見ることができて，楽しい．面白い．

Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity

論文紹介

Rahul Jain, Hartmut Klauck, Miklos Santha
http://arxiv.org/abs/1004.0105

上の「Constructive Proofs of Concentration Bounds」とも若干関係するが，optimal direct sum theoremというものが様々な計算モデルについて知られているようで，この論文ではそれがdecision treeに対しても成り立つことを示している．

Approximation Algorithms for Dominating Set in Disk Graphs

論文紹介

Matt Gibson, Imran A. Pirwani
http://arxiv.org/abs/1004.3320

平面上のdiskのintersectionグラフにおける最小支配集合問題がPTASを持つかどうかは大きな未解決問題であったが，この論文はそれを肯定的に解決している．去年のSoCGでChan & Har-PeledとMustafa & Rayが独立に提案した局所探索の枠組を使っている．ボロノイ図に着目したところがよかったんだと思う．

From Holant To #CSP And Back: Dichotomy For Holant$^c$ Problems

論文紹介

Jin-Yi Cai, Sangxia Huang, Pinyan Lu
http://arxiv.org/abs/1004.0803

最近dichotomy定理がどんどん出てきて，全く追えなくなってるので，もう一度ちゃんと復習しないといけないなと思っていても，どんどん出てくるという状況なのは，おそらく研究がかなり進展しているという証拠なのだろう．この論文ではHolant問題というある種の数え上げ問題 (関数問題といった方がよいかもしれない) の複素版に対するdichotomy定理を示している．

Spectral Methods for Matrices and Tensors

論文紹介

Ravindran Kannan
http://arxiv.org/abs/1004.1253

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

Optimal stochastic planarization

論文紹介

Anastasios Sidiropoulos
http://arxiv.org/abs/1004.1666

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

Index coding via linear programming

論文紹介

Anna Blasiak, Robert Kleinberg, Eyal Lubetzky
http://arxiv.org/abs/1004.1379

長くて読む気がなかなか湧かないけど．符号の問題．送り手はn個のメッセージx1からxnまでを持っていて，n人いる受け手はそれぞれxiを受け取りたい．そのとき，受け手は自分が受け取りたいもの以外のメッセージを既にいくつか知ってる，という状況を考える．そのような付加的な情報を使うと符号語長が短くて済むかもしれない，ということなのだそうだ．それがindex codingという話のようで，線形計画法を使って符号語長に対するよいboundを出そうという流れ．ちゃんと読んでないけども，Shannon容量と趣きが似ているかもしれないので，組合せ最適化をやってる人は要注目かもしれない．

Approximate Euclidean Ramsey theorems

論文紹介

Adrian Dumitrescu
http://arxiv.org/abs/1004.1654

幾何学的なRamsey理論はまだまだ未発達で未解決問題も多い，という状況はGrahamの書いた「Handbook of Discrete and Computational Geometry」の賞を見ても分かる．グリッドに対する幾何学的Ramsey理論は数論的な趣きがあるので，割と分かってきている．(それでもまだ不十分ではあるが．) この論文では，グリッドまで規則的ではないけれども，グリッドに近いものを考えていて，うまくばらまかれている大きな点集合がグリッドに近いもの必ず含む，ということを証明している．