論文紹介
Alexander Souza http://arxiv.org/abs/1202.0569タイトルを見て2つ驚いた．1つはCycle Double Cover Conjectureが解けたこと．もう1つはconstructiveであるということ．実はこんなタイトルがついているので，non-constructiveな証明が既に知られていたのか…
もうそろそろ書かないと，書く機会を失ってしまいそうなので，何とか書きます． 聞いてない話もありますし，聞いた話でも勘違いがあるかもしれないのは，いつも通りとします． Computing all maps into a sphere Martin Čadek, Marek Krčál, Jiří Matoušek, …
Gary McGuire, Bastian Tugemann, Gilles Civario http://arxiv.org/abs/1201.0749中身は読まず，アブストラクトしか読んでないけども，ヒントの数が16の数独は存在しない，ということを計算機による探索で確かめた，とのこと．計算機による探索といっても，…
William Gasarch http://arxiv.org/abs/1108.3347プログラムの停止性の証明にRamsey理論を応用する、という研究の紹介．複雑なRamsey理論を使うわけじゃないけど，個人的にこういうのは好き．実際に使われるようなプログラムとかアルゴリズムにこういうのが…
Rodney G. Downey, Dimitrios M. Thilikos http://arxiv.org/abs/1106.3161Parameterized complexityとFixed-parameter algorithmsのサーベイ．最近の成果まで載っているので，最新の動向に追い付きたい人にお薦め，といいたいところだけど，長い．それだけ…
David R. Wood http://arxiv.org/abs/1104.1243久々に．頂点数nのグラフが持つ極大独立集合の数が高々3^{n/3}であるという事実は今となってはよく知られているが，これに対する短い証明を与えている．たしか，MoonとMoserの証明はshiftingのようなことをして…
Daniel Kohen, Ivan Sadofschi http://arxiv.org/abs/1006.2571王様がn組のカップルを招いて食事をするとき (つまり2n+1人いるとき) に，各カップルiの2人の間の距離が決められた数d(i)にちょうどなるようにできるか，という問題． これについて「2n+1が素数…
Pandelis Dodos, Jordi Lopez-Abad, Stevo Todorcevic http://arxiv.org/abs/1006.2668バナッハ空間におけるラムゼイ現象について，どういう未解決問題があるのか述べている．バナッハ空間の用語が全然分からないので，中身がよく分からないけれども，組合せ…
Francisco Santos http://arxiv.org/abs/1006.2814以前書いたHirsch予想の反例．
Danny Hermelin, Chien-Chung Huang, Stefan Kratsch, Magnus Wahlstrom http://arxiv.org/abs/1006.20632人ゲームのナッシュ均衡の計算が，利得行列が「疎」である場合には多項式時間で計算できるということを示している．「疎」であることの定義は論文参照…
Shakhar Smorodinsky http://arxiv.org/abs/1005.3616著者がずっと研究している「Conflict-Free Coloring」に関するサーベイ論文．ワイヤレス・ネットワークやRFIDネットワークにおける問題のモデル化になっている．特に，幾何学的な側面に重きが置かれてい…
Jacob Fox http://arxiv.org/abs/1006.1300Graph removal lemmaはSzemerediの正則性補題の応用としてよく出てくるが，この論文ではSzemerediの正則性補題を使わずにgraph removal lemmaを証明する．ちょっと見てみたところ，アイディアとしてはSzemerediの正…
Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh http://arxiv.org/abs/1005.5449広いクラスのグラフ上の広いクラスの問題に対してEffcient polynomial-time approximation scheme (EPTAS) を与えている．広いクラスのグラフというのは…
Dana Moshkovitz http://eccc.hpi-web.de/report/2010/096/Schwartz-Zippelの定理 (補題) といえば，randomized algorithmの例としてよく出てくるものだが，その簡単 (3行ぐらい) の証明を与えている．確かに短く，簡単．
Milan Bradonjic, Aric Hagberg, Nicolas W. Hengartner, Allon G. Percus http://arxiv.org/abs/1005.5475Random Intersection Graphというものがあるようで，それの連結成分の進化に関する論文．Random Intersection Graph (RIG) とは次のように定められる…
Dion C. Gijswijt, Hans D. Mittelmann, Alexander Schrijver http://arxiv.org/abs/1005.4959A(n,d)で長さnの01列の集合で，どの2つの間のハミング距離もd以上であるものの最大サイズを表すとする．この論文では半正定値計画法を使って，様々なnとdの値に対…
Mikko Koivisto, Valentin Polishchuk http://arxiv.org/abs/1006.1998私たちの論文の改善だということなのですが，私たちはこの論文が間違ってるんじゃないかと思っていて，たくさんメールが飛び交っています．3人それぞれが間違ってると思ってるところが違…
Robert Gerbicz http://arxiv.org/abs/1004.4374Ramsey数の下界を更新．計算機支援．こういうのは小さな結果かもしれないけど，ちゃんと報告してもらうことは重要．
Anirban Dasgupta, Ravi Kumar, Tamás Sarlós http://arxiv.org/abs/1004.4240今度のSTOCに出てくる論文．Johnson-Lindenstraussの補題に出てくる射影行列をどれだけ疎にできるのか議論している．ハッシュ関数を使ったシンプルなアルゴリズムだけど，解析が…
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…
Chun-Cheng Lin, Hsu-Chun Yen, Sheung-Hung Poon, Jia-Hao Fan http://arxiv.org/abs/1004.2338グラフ描画 (graph drawing) のこういう論文はなんか好きです．根付き木のballoon drawingについてはこの論文の中身を見て下さい．根を中心して，その子供を同…
