研究

ハードコア関数の誤解(その三)

間が空いてしまいました.前回の続きです.このGoldreich-Levinの構成方法に対して,一般化した視点を与えたのが以下の論文です. T. Holenstein, U. Mauer, and J. Sjodin "Complete Classification of Bilinear Hardcore Functions", CRYPTO 2005 この論文…

ハードコア関数の誤解(その二)

前回のポストの続きです.前回紹介したGoldreich-Levinのハードコア関数はハードコア述語,つまり出力長が1ビットでした.ハードコア述語はある意味で1ビット分の擬似乱数を与えることになっています.しかし,たくさんのハードコアビットを同時に得られる方…

ハードコア関数の誤解(その一)

ハードコア関数について今まで思い違いをしていた点があったので,備忘録として書いておこうと思います.前提から書き始めると長くなってしまったので何回かに分けてポストします.ハードコア関数というのは暗号理論や計算量理論でしばしば現れる基本的な概…

戸田の定理の簡潔な証明

Lance Fortnow の論文リストを見ていたらこんな論文が. Lance Fortnow "A simple proof of Toda's theorem," Theory of Computing, 5(7):135-140, 2009. 所謂 "Toda's Theorem" というのは "" という結果ですが,この論文ではその前半部分である "" を半ペ…

SODA 2010

SODA 2010 の採録予定論文リストが公開されているようです.NIIの河原林さんの論文が四本も!

stacs.cls

かの著名な国際会議STACSは数年前からLNCSを離れて自前で会議録を出版していることは皆さんご存知かと思います.今回初めてSTACSフォーマットで投稿することを考えているのですが,幾分慣れていないので,自分用の防備録としてでもTipsを残しておこうと思い…

ISAAC 2009 Accepted Paper List

12月開催予定のISAAC 2009の採録予定論文リストが出たようです.参加する予定はないのですが,ハワイであるみたいですね.楽しそうです.招待講演に Ronald Graham の名前がありますねー.どういう講演だったか参加した人にあとで教えてもらおうと思います.…

講演依頼

10月初旬に大阪で計算量理論の入門について専門外の方々に講演することになりました.情報オリンピックの合宿でやった話をアレンジしようと思っています.以前のは高校生向けだったので,少し専門性の高い話題も入れようと思います.

ASIACRYPT 2009 accepted paper list

ASIACRYPT 2009 の採録予定論文が掲載されたようです.結構日本のグループの論文が通ってますね.おめでとうございます.

研究会発表

来週から久々の出張です.発表準備中.

研究会発表

気がつけば七月ですね.しばらく前にちょっとしたネタを考えまして,直近の研究会に発表を申し込んだまでは良かったのですが,その直後にその結果が既存の結果から自明に導出されることに気が付いてしまいました.そのためここしばらくその研究会発表のため…

マトロイド

秘密分散法の勉強をしていてマトロイドにぶつかりました.定義は分かるのですが,いまいち直観が湧かないんですよね,マトロイドって.やはり慣れが足りないせいでしょうか.

IND-CCA2ゲームについての疑問

ここから自分の疑問点なのですが,IND-CPAゲーム,IND-CCA1ゲームまでは割と自然な攻撃として受け取れるのですが,IND-CCA2ゲームについて何だか不自然な印象を受けています.IND-CCA2ゲームでは第二ステージでも復号オラクルにアクセスできるのになぜ挑戦者…

適応的選択暗号文攻撃

最近,公開鍵暗号の安全性に詳しい学生さんから適応的選択暗号文攻撃に対して識別不可能性を持つ公開鍵暗号系の構成方法についてレクチャーを受けていました.とても奥が深くて大変勉強になりました.ほっておくと忘れそうなので簡単にまとめておこうと思い…

RANDOM+APPROX 2009 accepted papers

RANDOM+APPROX 2009 採録予定論文リストが出ていますね.De & Trevisan の論文が気になるところです.extractor と hardness amplification が互いに関係があることは Vadhan のサーベイ論文にもあるように既知であると思いますが,それ以上の何か新しいこと…

情報統計力学

東工大の樺島先生が情報統計力学のお話を集中講義でされているので聴講してきました.今日の話題はランダムエネルギーモデルの分配関数の計算を通じてレプリカ法の使い方を学ぶという内容でした.基本的に理論計算機科学と似た感じの漸近的解析を行うのです…

セミナー

学生の研究セミナーで自分の詳しくない話題にちゃんとついていけていません.これはよくありません.

CRYPTO 2009 Accepted Paper List

CRYPTO 2009 の採録予定論文リストが出たようです.ゲーム理論ベースの結果が増えてきてますね.

級数の評価

ここ一週間ほど懸命にエントロピーがらみの級数の評価を行っていました.Stirling 近似公式を使いまくっていたのですが,英語版の Wikipedia と日本語版の Wikpedia で微妙に内容が違いますね.いずれにせよ当分見たくありません.

ゲーデル賞

もうあちこちで話題になっているようですが,今年のゲーデル賞は以下の二つの論文に決まったようです. (公式サイトはこちらです.) - O. Reingold, S. Vadhan, and A. Wigderson, "Entropy Waves, the Zig-Zag Graph Product and New Constant Degree Exp…

ぼちぼちお仕事再開

育児のため長らくお仕事をお休みしていましたが,そろそろ復帰することを考えないといけません.査読も引き受けちゃったし.久しぶりに行列式の計算をしようとしたら余因子展開のやり方を忘れていました.

続・NEXP探索問題

さて前回のエントリーの続きです.EXP=NEXPだった場合にはNEXP探索問題は指数時間で解けそうもない,ということでした.NP=Pの場合には降下型自己帰着によりNP探索問題はNP=Pの場合には多項式時間で解けるのですが,なぜ同じアプローチは通じないのでしょう…

NEXP探索問題

NP問題は良く知られているように降下型自己帰着(downward self-reduction)を持ちます.つまり,長さ以下のインスタンスの判定を行うオラクルがあれば,多項式時間で長さのインスタンスの判定を行うことが可能,ということです.分かり易い例でいうと充足可能…

続・育児と研究

結局残り一割のところにミスが見つかり,まわりまわって結局正しくなりそうなので,さらに証明をつめていく作業に入っています.日中は家事と我が子の世話をしつつ,彼が寝ている隙に研究を進める毎日です.

育児と研究

育児の合間に新しいネタを仕上げつつあります.(他にも科研費の報告書書きやらジャーナル投稿論文の修正作業やらあるのを尻目にですが・・・)九割方証明を終えてはいるのですが,いつも残り一割に落とし穴があるのです.慎重に詰めていかねば.しかしFOCS…

予想解決その後

やはりあと一歩のところでダメでした.でもアプローチとしては悪くなさそうなので,もう少し頑張ってみようと思います.

予想解決?

四半世紀ぐらい未解決の結構有名な予想が解決できた気がします.二日ほどしか考えていないのですが,本当に解決できたのか自分でも半信半疑なので慎重に証明を進めてみようと思います.

子守り研究者

子どもをあやしながらSkypeで学生の論文執筆指導.便利な世の中になったものです.

STOC 2009 accepted paper list

今更ですが,STOC 2009 の採録予定論文リストが公開されているようです.今回はアブストラクト付きです.

査読

と論文執筆にかまけていたら査読の催促が.すみません,ちょっと待って下さい.来週の頭までには・・・