2008-01-01から1年間の記事一覧
どうやら alternation を randomenss に変換するのは結構大変なようです．目だった結果としては Sipser の ぐらいみたいですね．こう見ると randomness というのはかなり特殊な計算資源なんだなー．
最近，ある意味 extreme な科学系ニュースがいくつか飛び交っていますね． Gizmode： ついに常温核融合を成功させた科学者は日本人 北海道新聞： 簡易炉で「常温核融合」か 北大院・水野氏が確認 国際学会で発表へ Gigazine： 水から電流を取り出すことを可…
まだ交代性Turing機械になりきれていないようです．量子計算機になりきれていなかった時代を思い出しました．日々精進です．
ここ一週間で二本ほど論文執筆＆投稿してました（どちらも主著者ではありませんが）．最近連敗気味なので好転すると良いのですが．
前回のエントリの続きです．さて Gowers norm というものが計算量理論でいろいろ応用できることを簡単に触れました．その Gowers norm の顕著な特徴として，高次の Gowers norm では低次多項式の影響が失われる，というものがあります．より具体的には，任意…
よく図形を斜線で塗りつぶすときに「／／／／／」あるいは「＼＼＼＼＼」の二通りを使うと思うのですが，これらを区別する一般的な名称ってあるのでしょうか？
Gowers一様性の Timothy Gowers って実は Bela Bollobas （組合せ論，グラフ理論で有名）の弟子だったんですね(Wikipediaより)．知らんかったー．
Gowers一様性の話を書きたいのですが，ここのところ論文書きで忙しいのと風邪を引いて体調を崩してしまい，滞ってます．もう少ししたら続きを書きます．
前回のエントリの肝心の中身について書こうと思います．そもそも Gowers uniformity norm というのは Gowers が Erdos-Turan conjecture の(Szemerediの定理として知られている)ある特殊ケースの別証明のために導入した概念です．一般的には以下のように定義…
Shachar Lovett, Roy Meshulam, Alex Samorodnitsky Inverse Conjecture for the Gowers norm is false 解説を少し書こうと思いましたが，書類書きで疲れているので明日中身を書きます．（これだけでも書いておくと自分へのプレッシャーにはなりそうです．）
香港でフカヒレ（胸ビレ＆背ビレ）を買ってきました．どうやって調理すればいいのかさっぱりです．調理方法をご存知の方はご一報を．
Internet WATCH の記事，産総研とヤフー、フィッシング防止技術の評価用ソフトウェアを公開，より 産業技術総合研究所（産総研）とヤフーは22日、フィッシング詐欺の防止技術「HTTP Mutualアクセス認証」を組み込んだWebブラウザ「MutualTestFox」と、Webサ…
しばらく香港にいます．
Terence Tao and Van Vu, "On random matrices: Singularity and Determinant" Terence Tao and Van Vu, "On the singularity probability of random Bernoulli matrices" 最近，（あまり進んではいないのですが）ランダム行列の解析に興味を持っていまして…
なんかバンバン来てます．これはまずいです．査読のペースを上げなければキュー長が発散してしまいそうです．
今日は新しい科研のプロジェクトに申請するための書類は一所懸命書いていたのですが，明日が別の科研費報告書の学内締め切りだったことに今頃気がついて，慌てて書類一式の準備をしました．危ない．
IWSEC 2008 の開催地が香川と聞き，これは讃岐うどんをしこたま食べられるチャンスだと随分前から考えていたのですが，投稿締め切りが次の金曜日と迫っているのにも関わらず良いネタが手元にありません．これは残念．
accepted paper list がトラックA,B,Cともに揃ったようです．
一件終わらせたらまた一件依頼が来ました．FIFOで頑張ります．
ITmedia News の記事より． 「LOGiN」が休刊へ あの「LOGiN」が、25年の歴史に幕を閉じる。 2008年04月11日 18時28分 更新 エンターブレインは、PCゲーム雑誌「LOGiN」（ログイン）を、5月24日発売号で休刊すると発表した。 LOGiNは1982年5月、アスキー（当…
今年も査読の季節がやって参りました．まだ今のところ２件だけですが．
せっかくブログをつけているのでエイプリルフールネタでも投下しようと画策していたのですが，「今年のゲーデル賞の内定貰いました！」とか「NP≠Pが証明されたようです！」とか月並みなネタしか思いつかずウンウン悩んでいるうちに日付が変わってしまったの…
Information-Theoretic Conditions for Two-Party Secure Function Evaluation Claude Crépeau, George Savvides, Christian Schaffner, Jürg Wullschleger EUROCRYPT 2006 の論文です．これまで提案されてきたいくつかの情報理論的安全性に関する二者間の安…
明日は量子計算絡みのワークショップで発表です．久しぶりに量子関係の話をすることに．ちょっと不安です．
スラッシュドットジャパン 40年近く答えの出なかった数学の難問が解かれる 昨日の記事ですが，Road Coloring Problem (Road Coloring 予想) と呼ばれるグラフ理論の定理が証明された事の紹介があったようです．グラフ理論については不勉強なもので今までこの…
最近忘却通信がらみの研究をやっているのですが，奥の深さに感心しています．安全性の定義だけでもかなりの紆余曲折があったみたいですね．
BPP の derandomization に関する Impagliazzo-Wigderson の結果が改良できたと思うのですが，まだ詳細を詰めることができていません．早めに証明を完成させねば．
明日の中高生向けの講義の準備が一応完了しました．三時間分新たに書き下ろしたので結構大変でした．NP vs. P 予想，ゼロ知識証明，PCPの話を紹介する予定です．帰着の概念の説明に良い具体例が見つかっておらずちょっとモヤモヤですが．
理由あって最近ギターを久しぶりに練習してます．暫く弾いてないと駄目ですねー．
三月中旬に量子計算関係のワークショップで発表しなくてはいけないことを思い出しました．最近学生さんと一緒にやっていることを話そうと思いますが，結果が間に合うかどうか．
