あちこちのブログでも話題になっていますが，今年のゲーデル賞は Alexander A. Razborov and Steven Rudich, "Natural Proofs," J. Comput. Syst. Sci. 55(1): 24-35 (1997) に贈られることに決まったそうです．私自身の内容についての知識は，計算量理論で…

富士通研の下山武司さんの講演があるということで茨城大の黒澤馨先生に声を掛けて頂いたので茨城大ひたちキャンパスまで聴講しに行ってきました．お話の内容は大きく分けて (1) 数体篩法の概要，(2) 素因数分解専用ハードウェアの設計，の二つです．素因数分…

Eric Siegel Educational Computer Science Songs 研究室の学生さんが発見してました．面白そうなので後で聞いてみようかと．

珍しい事にここ二日の間に別々の論文誌から三本も査読依頼が来ました．そして来週末までに仕上げないといけない論文が二本です．頑張ろう．

前々回の記事でFortnowのblogが終了したと書きましたが，早くも復活したようです．ただ書き手がWilliam Garsarchに代替わりしたみたいです．

この四月から助教になりました．って学生さんに話すと「助教授になられたんですか？おめでとうございます．」という反応が漏れなく返ってきます．助教というポスト，あんまり知られてないみたいですね．まぁ助手の名前が変わっただけです．助教授は今後「準…

Mac OS X プログラミング入門 Objective-C 荻原 剛志（著） 広文社授業の都合でCocoaを使わないといけなさそうな雰囲気．

Oded Regev, "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography," STOC 2005.主結果はGapSVPからランダム線型符号の復号問題への帰着であるが，これを基にGapSVPベースの公開鍵暗号系の構成を与えている． つまり，ある近似パラメ…

もうすぐ投稿予定の会議の締切が近いのですが，まだ証明が完了していません･･･今回はかなりまずいかも．気分転換に新居の裏にある満開の桜並木を散歩してきました．桜の花びらが舞う中での散歩って気分が良いものですね．ってああ科研費の報告書も書かなくち…

やっと引越しが終わって無事にネットも開通しました． ところで気が付いたらLance Fortnowの有名なブログが終了していました．結構初期の頃からの読者だったのですが，四年半も書き続けられていたのですね．これまで色々勉強になったのですがとても残念です．

最近は引越しの作業でドタバタしてて忙しいです．それはそうと最近符号理論の結果を色々使うこともあり，有限体の理論をちゃんと勉強しないとなー，という感に迫られているのですが，符号理論を専門とする皆さんは，どの辺りの教科書で有限体の基礎を勉強し…

V. Guruswami, C. Umans and S. Vadhan "Extractors and condensers from univariate polynomials." CCC 2007に採録された論文．最適なパラメータを達成するrandomness extractorとloss-less condenserを以前の多変数多項式符号(Reed-Muller)に基づく構成と…

以前の日記で書いたTuring賞受賞者Frances Allen氏のインタビュー記事． "数学教師からチューリング賞受賞者になるまで"

今日たまたまゲストとして訪問されていたDieter van Melkebeekさん*1とお話できる機会があったので，今やってる平均計算量の結果（昨日ギリギリで新しいアイデアが出て何とかまとめられたものだったのですが）を聞いて頂きました．２時間程のディスカッショ…

平均計算量理論の研究を現在進行形でやってるわけですが，基本的な知識に抜けが多すぎるので，このサーベイ論文で勉強しなおすことにしました． A. Bogdanov and L. Trevisan, "Average-Case Complexity" 平均計算量の基本的な概念や重要な結果が分かり易く…

今年のTuring賞受賞者が決まったみたいですね． Frances E. Allen For pioneering contributions to the theory and practice of optimizing compiler techniques that laid the foundation for modern optimizing compilers and automatic parallel executi…

最近 accepted paper list ばっかり載せていますが，今回はSTOC 2007です．量子計算関係（だと思われるもの）は以下の４本でした． F. Magniez, A. Nayak, J. Roland and M. Santha, "Search via Quantum Walk." D. Gavinsky, J. Kempe, I. Kerenidis, R. Ra…

採録論文リストが出たようです． 個人的には Secure Computation from Random Error Correcting Codes H. Chen, R. Cramer and S. Goldwasser, R. de Haan and V. Vaikuntanathan が気になります．最近はボスとの共同研究で平均計算量絡みの研究で忙しいです…

次回の Computational Complexity Conference の採録論文リストが公開されたみたいです．

長崎で開催されていた学会から戻ってきました．大変有難いことに論文賞を頂きました．賞を頂くのは初めてなので，非常に嬉しいです．また来年も頑張って良い論文を投稿しようと思います．また月曜日から別の学会参加のため京都出張です．まぁ話す内容は同じ…

明日から学会参加のため，長崎へしばらく出張します．ちゃんぽん食べたい．

今日，大学にAlan C. Kay氏*1が来ているということで講演を聴きに行きました．主な内容としては彼が主導している"SQUEAK"というシステムに関する解説でした．感心したのはそのシステムの開発の動機です．近所の人や友人に「最近新しいコンピュータを買ったん…

大学の生協で２冊ほど文庫本を購入しました． アフターダーク，村上春樹著 哲学入門，バートランド・ラッセル著，高村夏輝訳 前者は妻が村上春樹のファンという影響を受けまして，ちょくちょく彼の小説を読むようになっていたのですが，この本をまだ購入して…

ECCCをチェックしてたら，こんな論文が･･･R. Santhanam, "Circuit Lower Bound for Merlin-Arthur Classes"メインの結果は非常にシンプルで，MA/1がP/polyに含まれない，つまり，1ビットアドバイス付きMAに属する言語で多項式サイズ論理回路で計算できない言…

NEC，商用の光通信ネットワーク上で稼動する量子暗号生成システムを開発実環境下での量子鍵配送の実装に関するプレスリリースがNECとJSTから出たようです．元・中の人なんで，こういうニュースがスラドとかに取り上げられているのを見るとちょっと嬉しいです…

今日，量子計算のプレプリントサーバに C. Moore, A. Russell, and U. Vazirani, "A classical one-way function to confound quantum adversaries" という論文がアップロードされていました．以前から狙っていたテーマにかなり近いことを先にやられてしまっ…

最近は暗号の基礎理論に絡む（特にクラスNP周辺の）平均計算量について構造的計算量理論の立場から研究を進めています．近年のこの辺りの研究分野の発展は非常に目覚しく，新しい手法が目白押しのようです．理論自体も相当なスピードで高度化しているのでフ…

何とか某暗号系会議に論文を採録してもらいました．（と言っても二本投稿して片方は落とされてしまいましたが･･･）中国を訪れるのは初めてなので少々楽しみです．