吉田です。最近ACM Symposium on Theory of Computing (STOC)という学会に投稿していた論文が受理されました。論文はECCCにアップロードしています。STOCは次回が43回目の開催となる理論計算機科学(要するにアルゴリズムと計算量を扱う分野)の中では最高峰の学... 続きを読む

• research.preferred.jp
• 学び

_ [研究] STOC3日目 8:45-10:45 Markov Chainsのセッションにいた。 Ravi Montenegro and Prasad Tetali, How Long Does it Take to Catch a Wild Kangaroo? a,b,pが与えられてa^x=b(mod p)なるxを求めたい。 で、これにはPollard's Kangaroo法というアルゴリズ... 続きを読む

• mono.kmc.gr.jp:oxy
• テクノロジー

8:45-10:45 Graph Cuts and Flowsのセッションにいた。 Luca Trevisan, Max Cut and the Smallest Eigenvalue. 連結なグラフの隣接行列の固有値のうち最小のものをλnとおく。そうするとλnが大きいほど、グラフが二部グラフっぽい形をしていることを示して、それ... 続きを読む

• mono.kmc.gr.jp:oxy
• テクノロジー

_ [研究] STOC 2009 STOC 2009に参加中です。感想を色々なところで披露することになっているので、ここにメモを残しておくことにします。たぶん技術的な内容に関しては嘘だらけだと思います。 _ [研究] STOC -1日目 (5/30@日本) よくあることなのだが電源を持っ... 続きを読む

• mono.kmc.gr.jp:oxy
• テクノロジー

文字列らしきものは1件のみApproximating Edit Distance in Near-Linear Time Alexandr Andoni and Krzysztof Onak編集距離を求める問題は動的計画法を用いてO(n^2)で解くのが常道で，高速化の手法としては，ビット並列を用いてワード長で割る技術や，網羅的に... 続きを読む

• d:id:zeppeki
• テクノロジー

_ [研究室] STOC Accepted PapersSTOCのAccepted Papersが出たので、特に興味があるものを書き記しておきます。やはりブレイクスルーを感じるものが多い。 On Proximity Oblivious Testing Oded Goldreich and Dana Ron 作りたいのはある性質を満たすか、その性... 続きを読む

• mono.kmc.gr.jp:oxy
• テクノロジー

_ [研究室] STOCの論文の内容STOCに採択された論文ですが、論文そのものは少し手直しをしたいのでまだWebには公開しません。もし欲しい方がおられましたら個別にメールをください。では折角の機会なので、内容を大雑把に説明してみます。あまり正確な書き方はし... 続きを読む

• mono.kmc.gr.jp:oxy
• テクノロジー