前回のポストの続きです．前回紹介した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 の採録予定論文リストが公開されているようです．NIIの河原林さんの論文が四本も！

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

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