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

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

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バナッハ空間におけるラムゼイ現象について，どういう未解決問題があるのか述べている．バナッハ空間の用語が全然分からないので，中身がよく分からないけれども，組合せ…

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

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

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人それぞれが間違ってると思ってるところが違…

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

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

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

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

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

再投稿完了．

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

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

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

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

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

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