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

supercon

予選結果を応募者に送付しました.ご確認下さい.倍率は約2倍といったところです.応募して下さった皆さん,ありがとうございました.本選出場の皆さん,8月にお会いしましょう.

授業 第11回目

アダマール行列について.授業の最後で扱った最大カットへの応用はpairwise independenceを用いたderandomizationの好例になってる. アダマール行列の情報は http://www2.research.att.com/~njas/hadamard/ にある.

A New Approach on the Seating Couples Problem

Daniel Kohen, Ivan Sadofschi http://arxiv.org/abs/1006.2571王様がn組のカップルを招いて食事をするとき (つまり2n+1人いるとき) に,各カップルiの2人の間の距離が決められた数d(i)にちょうどなるようにできるか,という問題. これについて「2n+1が素数…

supercon

ただいま予選審査中.結果通知は来週です.

Banach spaces and Ramsey Theory: some open problems

Pandelis Dodos, Jordi Lopez-Abad, Stevo Todorcevic http://arxiv.org/abs/1006.2668バナッハ空間におけるラムゼイ現象について,どういう未解決問題があるのか述べている.バナッハ空間の用語が全然分からないので,中身がよく分からないけれども,組合せ…

プログラム

たくさんシェルスクリプトを書いた.

授業 10回目

今回扱ったflipping card gameは案外面白い.

A counterexample to the Hirsch conjecture

Francisco Santos http://arxiv.org/abs/1006.2814以前書いたHirsch予想の反例.

Parameterized Two-Player Nash Equilibrium

Danny Hermelin, Chien-Chung Huang, Stefan Kratsch, Magnus Wahlstrom http://arxiv.org/abs/1006.20632人ゲームのナッシュ均衡の計算が,利得行列が「疎」である場合には多項式時間で計算できるということを示している.「疎」であることの定義は論文参照…

Conflict-Free Coloring and its Applications

Shakhar Smorodinsky http://arxiv.org/abs/1005.3616著者がずっと研究している「Conflict-Free Coloring」に関するサーベイ論文.ワイヤレス・ネットワークやRFIDネットワークにおける問題のモデル化になっている.特に,幾何学的な側面に重きが置かれてい…

A new proof of the graph removal lemma

Jacob Fox http://arxiv.org/abs/1006.1300Graph removal lemmaはSzemerediの正則性補題の応用としてよく出てくるが,この論文ではSzemerediの正則性補題を使わずにgraph removal lemmaを証明する.ちょっと見てみたところ,アイディアとしてはSzemerediの正…

Bidimensionality and EPTAS

Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh http://arxiv.org/abs/1005.5449広いクラスのグラフ上の広いクラスの問題に対してEffcient polynomial-time approximation scheme (EPTAS) を与えている.広いクラスのグラフというのは…

An Alternative Proof of The Schwartz-Zippel Lemma

Dana Moshkovitz http://eccc.hpi-web.de/report/2010/096/Schwartz-Zippelの定理 (補題) といえば,randomized algorithmの例としてよく出てくるものだが,その簡単 (3行ぐらい) の証明を与えている.確かに短く,簡単.

Component Evolution in General Random Intersection Graphs

Milan Bradonjic, Aric Hagberg, Nicolas W. Hengartner, Allon G. Percus http://arxiv.org/abs/1005.5475Random Intersection Graphというものがあるようで,それの連結成分の進化に関する論文.Random Intersection Graph (RIG) とは次のように定められる…

プログラミング

計算結果のログファイルでディスクが溢れそうになった.危ない.

Semidefinite code bounds based on quadruple distances

Dion C. Gijswijt, Hans D. Mittelmann, Alexander Schrijver http://arxiv.org/abs/1005.4959A(n,d)で長さnの01列の集合で,どの2つの間のハミング距離もd以上であるものの最大サイズを表すとする.この論文では半正定値計画法を使って,様々なnとdの値に対…

査読

溜まってるものはどんどん終わらせましょう.

Geodesic diameter of a polygonal domain in O(n^4 log n) time

Mikko Koivisto, Valentin Polishchuk http://arxiv.org/abs/1006.1998私たちの論文の改善だということなのですが,私たちはこの論文が間違ってるんじゃないかと思っていて,たくさんメールが飛び交っています.3人それぞれが間違ってると思ってるところが違…

授業 9回目

線形代数.いつもながら難しかったか.

プログラミング

書きかえれば書きかえるほど,違った出力をだしていく.困った.

3rd CompView Fall School on Algorithmic Bioinformatics

http://compview.titech.ac.jp/Members/okamotoy/3rd-compview-fall-school-on-algorithmic-bioinformatics9月1日〜3日に開催します.今,席は十分に空いています.詳細は私まで直接お問い合わせください.

プログラミング

バグは取れた.正確に言うと,Javaで書きなおしたらうまくいった.思ったよりも遅くないので満足.でもまだまだ改善しないといけない.

プログラミング

自分で書いたプログラムを動かしていたらバグを発見.しかもそのバグがとれない.困った.

論文改訂

再投稿完了.

査読

滞っているものを少しやる.あんまりやる気がでないところが辛い.

受理報告

受理された.国際会議だけど,忙しい時期なのでいかない予定.でも,受理論文一覧を見るととても楽しそうな気はする.

授業 8回目

デザインの2回目.主に射影平面について.いつもながら単調になってしまった気がする.もう少しメリハリを持たせたい.

東大駒場

コマゼミで駒場へ.久々にいったら,ホッケー場が人工芝になってて驚いた.

EATCS

EATCSのトップページに自分の名前が出てて驚いた. http://www.eatcs.org/

「本学卒業生が内閣総理大臣に」

http://www.titech.ac.jp/topics/news/detail_1157.html?id=topics本学元教官の次は本学卒業生です.