2010-04-01から1ヶ月間の記事一覧

Supercon

6月1日に予選問題発表です.いまはその準備.

ポリコム

電話をして北大につないでもらう.前回ほどは切れなかったけど,やっぱり切れる.

生協

注文した本を取りにいったら,「吉岡」という札がついているところから本が出てきた.そういう間違い方があるのか.

ディスカッション

T先生とT先生がいらっしゃってディスカッションするという話をM先生からお聞きして,混ざる.私の貢献は計算したことだけ.

New lower bounds for classical Ramsey numbers

Robert Gerbicz http://arxiv.org/abs/1004.4374Ramsey数の下界を更新.計算機支援.こういうのは小さな結果かもしれないけど,ちゃんと報告してもらうことは重要.

A Sparse Johnson--Lindenstrauss Transform

Anirban Dasgupta, Ravi Kumar, Tamás Sarlós http://arxiv.org/abs/1004.4240今度のSTOCに出てくる論文.Johnson-Lindenstraussの補題に出てくる射影行列をどれだけ疎にできるのか議論している.ハッシュ関数を使ったシンプルなアルゴリズムだけど,解析が…

授業 3回目

前回の壊滅的ダメージからは立ち直れました.これぐらいの分量がちょうどよいということでしょうか. ちなみに,今日の授業の隠しテーマがrandomized algorithmとderandomizationだったということはあまり気付かれなかったかもしれないです. 授業では確率の…

ポリコム

北大と接続.なぜか接続がすぐ切れてしまって,思うように会話できない.

発表準備

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

Approximate Euclidean Ramsey theorems

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

Index coding via linear programming

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

Optimal stochastic planarization

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

Spectral Methods for Matrices and Tensors

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

授業準備

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

The Dichotomy of List Homomorphisms for Digraphs

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

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定理がどんどん出てきて,全く追えなくなってるので,もう一度ちゃんと復習しないといけないなと思っていても,どんどん出てくるという状況なのは,おそらく研究がかなり…

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とMusta…

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というものが様々な計算モデルについて知られているようで,この論文ではそ…

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 …

The Chordal Graph Sieve: Lower Bounds

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

授業 2回目

壊滅的な自損事故を起こした.次回は回復しますように.

授業準備

2週目にしていきなり自転車操業か.

Complexity Analysis of Balloon Drawing for Rooted Trees

Chun-Cheng Lin, Hsu-Chun Yen, Sheung-Hung Poon, Jia-Hao Fan http://arxiv.org/abs/1004.2338グラフ描画 (graph drawing) のこういう論文はなんか好きです.根付き木のballoon drawingについてはこの論文の中身を見て下さい.根を中心して,その子供を同…

Polynomial Time Algorithm for Graph Isomorphism Testing

Michael I. Trofimov http://arxiv.org/abs/1004.1808グラフ同型性問題を多項式時間で解くといっていて,にわかには信じられないのだけども,謝辞を見るとこの分野の大御所が名を連ねているので,読んでみる価値はあるかもしれない.私は読んでないけども.…

Are there any good digraph width measures?

Robert Ganian, Petr Hliněný, Joachim Kneis, Daniel Meister, Jan Obdržálek, Peter Rossmanith, Somnath Sikdar http://arxiv.org/abs/1004.1485グラフの木幅 (treewidth) の果たす役割はグラフ理論,グラフ・アルゴリズムの世界ではとても大きいが,その…

Limits of kernel operators and the spectral regularity lemma

Balazs Szegedy http://arxiv.org/abs/1003.5588論文がスタックにたまってきたので,ちょっと吐き出します.まだ溜まってますが.これは,いわゆるSzemerediのregularity lemma (正則性補題) を解析の観点から見直して,そのスペクトル版を証明する,という…

秋学校準備

本年度も開催するので講師依頼など.詳細が決まりましたらまたこちらで連絡します.

数学セミナー 5月号

数学セミナー 2010年 05月号 [雑誌]出版社/メーカー: 日本評論社発売日: 2010/04/12メディア: 雑誌購入: 1人 クリック: 12回この商品を含むブログ (1件) を見る書籍じゃないですが...恥知らずにも,「フォン・ノイマン」に関する記事を書きました.情報科…

授業1回目

とうとう開始.どうも丁寧さが足りなかったようなので,次回から気を付ける.おそらく準備が雑なんだと思う.はい. 授業のページは http://www.is.titech.ac.jp/~okamoto/lect/2010/dmcs/ です.

Logspace Versions of the Theorems of Bodlaender and Courcelle

Michael Elberfeld, Andreas Jakoby, Till Tantau ECCC TR10-062木幅を計算するためのBodlaenderのアルゴリズムと,木幅定数の性質でMonadic Second Order Logicで書けるものを判定するCourcelleのアルゴリズムの対数領域版を示している.対数領域アルゴリズ…