今日トレーニングしてるときに突然思いついた．思いつきなので実際に研究進めてみないと面白いかどうかわからないけど，とりあえず数日考えようか．他にも考えなくちゃいけない問題たくさんある気もするけど．

うーん，NP完全性ってどれくらい常識なんだろうか．定義せずに使いたいけど．

数学セミナー 2007年 12月号 [雑誌]出版社/メーカー: 日本評論社発売日: 2007/11/12メディア: 雑誌 クリック: 2回この商品を含むブログ (1件) を見る根本先生の二千円札の価値に関する記事や宮代先生の問題が出ています．

久しぶりに若干複雑なプログラムを書いていて，バグがなかなかとれなくて時間をつかっています．ちょっとしんどいですね．

ケーキ分割の問題について．公平分割，無羨望分割のアルゴリズムを紹介．学生には難しかったかもしれないけど，難しいぐらいがちょうどいいかも．

特集「自然言語とコンピュータ」で，他のことをしないといけないにも関わらず，読んでしまった．最適化やアルゴリズムの人が貢献できるところがもちろんあるので，自分としてはどこまで深く踏み込むかっていうところ．

Encyclopedia of Algorithms (Springer Reference)作者: Ming-Yang Kao出版社/メーカー: Springer発売日: 2008/07/01メディア: ハードカバー クリック: 16回この商品を含むブログ (2件) を見る日本語にすると「アルゴリズム百科事典」ということになるんでし…

共著者の方々から論文校正がばんばんやってきた．前のバージョンを読む前に次のが来たり，とか．なかなかフォローするのが大変．

査読が終わると査読が来る．

なぜかほとんど一日中プログラムを書いていた．ショートコーディングしたり，とか．

今週は査読を中心に行なっていく予定です．今月〆切のものが多いので．とりあえず1つ終了．この論文はテクニカルな意味で割と読みにくかった．

Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)作者: J. Flum,M. Grohe出版社/メーカー: Springer発売日: 2006/03/15メディア: ハードカバー クリック: 4回この商品を含むブログ (2件) を見るW[1]完全性などに…

Information Processing Letters，今年の10月から12月まで． An improved upper bound on the queuenumber of the hypercube Toru Hasunuma and Misa Hirota Information Processing Letters Volume 104, Issue 2, 16 October 2007, Pages 41-44 http://dx.d…

Information Processing Lettersの今年7月から9月までを見ていきます． Average-case analysis of QuickSort and Binary Insertion Tree height using incompressibility Brendan Lucier, Tao Jiang and Ming Li Information Processing Letters Volume 103,…

構想5年，ようやく書けました．

だいたい書けた．後は細かいところの修正や，図を入れたり，と．

Probability and Computing: Randomized Algorithms and Probabilistic Analysis作者: Michael Mitzenmacher,Eli Upfal出版社/メーカー: Cambridge University Press発売日: 2005/01/31メディア: ハードカバー購入: 3人 クリック: 60回この商品を含むブログ …

他にすることがいろいろあるような気がするけども，最近あまり論文を読んでいないと思い，とりあえずInformation Processing Lettersの今年上半期の目次と興味のあるアブストラクトを眺めてみることに． Simple deterministic wildcard matching Peter Cliff…

なんと，OR辞典2007がwikiとして，そして，ORアーカイブ集なるものがセットアップされたようです．また驚きました．

よくあることだけども，書いてるうちにどんどん証明が簡素化されていって，見た目の上では証明が一段と簡単に思えてきてしまう．

また引き受けてしまった．一年後ぐらいのことだけど．

http://www-06.ibm.com/jp/company/society/science/ichiran.shtml定兼先生，受賞おめでとうございます．

Algorithmic Game Theory作者: Noam Nisan,Tim Roughgarden,Eva Tardos,Vijay V. Vazirani出版社/メーカー: Cambridge University Press発売日: 2007/09/24メディア: ハードカバー購入: 1人 クリック: 5回この商品を含むブログ (2件) を見るアルゴリズム的ゲ…

東工大のグローバルCOEでポスドクを募集しているようです． http://compview.titech.ac.jp/office-pub/pd-recruit 文部科学省のグローバルＣＯＥの１つとして「計算世界観の深化と展開」（東京工業大学，拠点リーダ渡辺）が採択され，２００７年度７月からス…

最近，変な計算量理論クラスにはまりだしている．抜け出せなくなるかもしれないから気をつけないと．(別に悪いことではないからいいんだけど．)ところで，計算量理論クラスといえばComplexity Zooです．

昨日，東工大のセミナーで話をさせていただきました．ちょっと駆け足になってしまって分かりにくくなってしまったかもしれません．いろいろと思わぬ驚愕やプレッシャーがあって，少々戸惑いましたが．

論文を書いてるけど，締め切りに間にあわないかもしれない．頑張らないと．

Adrian Dumitrescu, Micha Sharir, Csaba D. Toth http://arxiv.org/abs/0710.4109 驚きました．内容は平面上のn点が定める単位面積三角形の数の上界の改善．私も何度もトライしたけど，全然できませんでした． 驚いたのは証明が非常にシンプルなこと．2ペー…

先週末から今週半ばにかけて何度も東京にいきます．

数日前に出した「オーダー記法：ちょっとしたクイズ」ですが，いろいろコメントをいただきました．ありがとうございます．たぶん聞き方が悪かったのかと思いますが「どこがまちがっているでしょう？」という問題なので，どこが間違っているのか，その箇所を…