2010-04-21
Klaus Dohmen http://arxiv.org/abs/1004.3416 Chordalグラフのクリークの族に対して，Bonferroniの不等式のようなものが成り立つ，ということを言っている．いわゆる包除原理は球体 (ball) のcontractibilityと同じことをいってるようなものなので，chordalグラフのクリーク複体がcontractibleであるということを知っていれば (これは私が関連する論文を書いたEdelman-Reiner ('00) の結果である)，この論文の結果はさほど驚きではない，と思う． Russell Impagliazzo, Valentine Kabanets http://eccc.hpi-web.de/report/2010/072/ さて，離散数学における確率論的手法の分野において「constructive proof」が最近注
2010-04-15
Balazs Szegedy http://arxiv.org/abs/1003.5588 論文がスタックにたまってきたので，ちょっと吐き出します．まだ溜まってますが． これは，いわゆるSzemerediのregularity lemma (正則性補題) を解析の観点から見直して，そのスペクトル版を証明する，というもの． こういうのがすらすら読めないと本当はいけないんだけど，そういうところにまで自分は達していない． Robert Ganian, Petr Hliněný, Joachim Kneis, Daniel Meister, Jan Obdržálek, Peter Rossmanith, Somnath Sikdar http://arxiv.org/abs/1004.1485 グラフの木幅 (treewidth) の果たす役割はグラフ理論，グラフ・アルゴリズムの世界ではとても大
2009-12-07
Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer http://arxiv.org/abs/0911.5526 計算量理論の研究者がSDPの研究をしているということを最適化の研究者はあまり知らないと思う．もちろん最適化の研究者は実際の計算に興味のある場合が多いが，一方，計算量理論の研究者は出現するSDPを解析することに興味がある，という点で立場の違いは見える． この話の出発点はGoemans-Williamsonによる最大カット問題に対する近似アルゴリズムであり，その偉大さが分かる．これについては中大の松井先生がOR学会誌に書いた解説が10年程経ったいまでも素晴らしい． その後，unique games conjectureとかmetric embeddingの研究の進展があって，SDPがこのような問題の本質に深く関わって
2006-10-18
最近、ジャーナルや会議論文集のチェックを細かくする時間がうまくとれなくなってきたので、メールでのalertサービスに申し込みました。 とりあえず、SpringerLinkとElsevierのsciencedirectは完了。 オーストラリア原稿。大幅な書き直しにより大変。
okamoto7’s blog
高等学校情報/情報の科学/負数と小数のデジタル表現 - Wikibooks の「関連する用語」の記述がひどい，と私の中で話題に． そこでは次のように書かれています． さて、情報科学で「ガロア体」（ガロアたい）という用語があるのだが、その正体は、単なる合同式、もしくは、その合同式の理論を必要に応じて定義拡張しただけのものである。 ガロアというと、数学史などでも紹介される偉大な天才数学者だが、しかし「ガロア体」という用語は、かってに情報科学者どもが使ってるだけな用語なので、もし大学などでガロア体という用語を聞いたら「でも単なる合同式だろ」と読者は脳内で置き換えよう。 ※ けっして独自研究でwikibooks編集者の「『ガロア体』なんて概念は無駄だし、存在しない」とか（独自研究で）言ってるのでなく、出版社名は忘れてしまったが2001年ごろに出版されていた離散数学（りさんすうがく）の大学1年レベル
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Peter Winkler - okamoto7’s blog
