ref:FOCS 2008 - Accepted Papers Tali Kaufman and Shachar Lovett. Worst Case to Average Case Reductions for Polynomials Stefan Dziembowski and Krzysztof Pietrzak. Leakage-Resilient Cryptography in the Standard Model Dan Boneh, Periklis Papa…

p:素数, p|nとする. を示せ. 某講義ノートに証明無しで書かれていて困った. p≠nは必要ない. イコールの場合は両辺ともに1なので問題なし Hさんの解答 である. もしpがnの最小の素因数であれば, 右側のn/p以外の項の分子からnを除いても良い (modulo nで考え…

今年はR. M. Karpだそうで. リチャード・マニング・カープ Richard Manning Karp - 第24回(2008)京都賞 先端技術部門ref:Computational Complexity: Karp Wins Kyoto Prize!

家で結果を纏めているところ. 書くの面倒くさい(;´Д｀) ePrintの方にCRYPTO 2008に出るものがちらほら [0806.2947] A Syntactico-Semantical Bi-Polar Disorder FLP Paradox Implies SAT is NOT NP-complete, P vs. NP does not exist, and ZFC is Inconsist…

B1-2向け.DFA用のポンピング補題は割と簡単に証明が出来ます. 状態数以上の文字列をDFAに入力として与えたときには, 鳩ノ巣原理より, 必ずどこかの状態を2回通っているということが直観です. 反復補題とも言われる様子 (→正規言語の反復補題 - Wikipedia)ポ…

海の向こうではSTOC 2008が終わる頃か 証明はシンプルだけど見地が良いという論文をどうするか問題があったらしい See Computational Complexity: STOC Business Meeting, Part I TheoryWikiを作ろうという話にはWikipediaの管理者が出張ってきてるようだ 出…

マルバツゲーム：賢いプレイヤー どう書く？org 必勝法を中学校の数学の授業中に全探索したなぁと思いつつ解いていない. 先手・後手が最善で打っていくと引き分けになる.

公開鍵暗号方式の場合, 安全性について議論するときにセキュリティパラメータを入れて議論する. よって, そもそも鍵空間が無限大という話は酷くおかしい. ということを分かり易く伝えなければアウトリーチと言えないのか. これは面倒臭い. もうちょっと真面…

タワー表記かよ. 実はあっさり解ける問題. (define (find a b n) (define (order a n) (let loop ((i 1) (c a)) (if (= c 1) i (loop (+ i 1) (remainder (* c a) n))))) (if (= b 1) (remainder a n) (let1 o (order a n) (expt-mod a (find a (- b 1) o) n…

Problem 135 Problem 136 x^2 − y^2 − z^2 = nについて正の項からなる等差数列(x,y,z)を解として考える. 135は10^6未満のnで解がぴったり10個になるものの数. 136は5*10^7未満のnで解が一意に定まるもの. 手を動かすとアレの解の構造を決定する問題になるの…

まだalpha版らしい. 個人のブックマークも出来るらしい. 情報系としてはありがたい.

AND, OR, NOTからなるn入力1出力サイズsの回路の数の上限は, 2^s (2+2n+s)^s2^s (2+2n+s)^{2s}. 素子の数をk, ファンインの数を高々mにして同様の上限を考えると, k^s (2+2n+s)^sk^s (2+2n+s)^{ms}.

暫く機能停止らしい. やっとx>y>z>0が等差数列でx^2-y^2-z^2=n (Prob 135, 136) が分かったというのに.

Problem 157は面白かった. アルゴリズムを改良するとまだまだ縮みそうではあるが本業の方をいい加減やらないといけないので改良は止めておく. gosh> ;(time (apply + (map (lambda (n) (length (solve n))) (iota 9 1)))) ; real 38.250 ; user 37.843 ; sys…

暗号の安全性は一種の学習不可能性だよという話を先生からよく聞くのだが, 学習不可能性を暗号の安全性から示したのって, 格子系以外だと何かあったっけかな. 暗号→学習不可能性の話はECCC 2005辺りに載ってる筈. 逆はHBプロトコルの安全性やRegev05とかがそ…

108と110. 1/x + 1/y = 1/n で, 0 < x <= yという整数解の個数に関する問題. 解の構造は分かった. ぱっと思いつく方法だと1分ルールに反するので, 逆を考えるべきなのだろう. そういう方針であれば110の方も何とかなるのかな. 多分.またRioさんに離された. …

127問. Repunit系は129だけ残ってしまった. 位数を求めるのは面倒臭いなぁ. PROB119はこっちの方向が良いんだな. num->digitsは各桁にばらす関数 (use srfi-42) (list-ref (sort (list-ec (: b 2 1000) (: e 1 50) (if (and (> (expt b e) 10) (= b (apply +…

総合大会中に多少解いてたらしい. ようやく122問. Problem 26 面倒臭がって残していただけ. Problem 93 0除算? +inf.0になるからGaucheだと大丈夫. Problem 164 数え上げ. 漸化式を立ててメモ化で終了.

404 Blog Not Found:アルゴリズム - 合コンの効用を最大化する 安定結婚問題が取上げられているので情報の添加.Iwama, K., Manlove, D. F., Miyazaki, S. and Morita, Y. “Stable Marriage with Incomplete Lists and Ties” (ICALP 99) によれば, リストに異…

理系のための口頭発表術 - 4403 is writtenでお薦めされていた本が生協にあったので買って読んでみた. 理系のための口頭発表術―聴衆を魅了する20の原則 (ブルーバックス)作者: R.H.R.アンホルト,鈴木炎,I.S.リー出版社/メーカー: 講談社発売日: 2008/01/22メ…

112問. 数え上げに関する問題を解いた. 113, 114, 115とか.

Problem 94 L-L-(L+1)またはL-L-(L-1)の三角形で面積が整数になるものを探索. 思いついてからも計算ミスで詰まってた. Problem 98 試行錯誤で解いた. 全然面白くない. Problem 100 分かれば簡単. Problem 111 cartesian-productとcombinationsのおかげで大分…

やっとこさ98問100問. Problem 72 手元の計算結果では一番高速なものでgauche, Pen 4 3GHzで2.781s. Problem 79 手計算の方が速い. Problem 80 SICPで課題問題だったと思うんだが. 普通にdecimalクラスを作って例の方法で近似. 2乗根の場合は古くから使われ…

I. Dinur, E. Grigorescu, S. Kopparty, and M. Sudan “Decodability of Group Homomorphisms beyond the Johnson Bound” 概要を読む限りではHadamard符号を抽象化したもののリスト復号ぽい. Goldreich-LevinやKushilevitz-Mansour, Akavia-Goldwasser-Safra…

参考: d:id:odz:20080229:1204287954 Project Euler用のメモ 100万までの各数について真の約数の和を求めることを考える. C系だとこんな感じ. long[] a; a.length = 1000000; for (long i = 2; i < 1000000; i++){ for (j = 2; j * i < 1000000; j++){ a[j *…

84問. ポインタも分からぬままC++の練習としてProblem 23とProblem 70を解いた. ポインタを使うところが無かったのでまぁいいのか. 言語を変えると力技で解けるってのはどうかと思った. Problem 70はあと一歩でC++を使うことなく解けたらしい. Problem 89がW…

80問ヽ( ´ー｀)ノ 最初の方の簡単な問題を解き忘れていたので解いた.

RSAでm^e mod n = mとなるmの個数を最小化するeの総和を求める問題. 暗号屋としては解かねばなるまい. 数論系の暗号は久しぶりなのでちょっと迷ったが, 一応解いた.

70問( ´ー｀) 801-900に入った. 条件付き最短パス探索問題 (Problem 81とProblem 82) は面白いな. n次正方行列について, Problem 81は計算回数がO(n^2)のアルゴリズムか. Problem 82はO(n^3)のしか思い浮かばなくて80s位掛かる. もう少し練るべきか. 条件の…

A remark on primality testing and the binary expansion « What’s new 論文の方を読む気はしないが面白い結果だなー. 十分大きなnについてnビットの素数pが存在し, i=0,...,n-1についてp \pm 2^iは全て合成数. 決定的な素数判定では全ビット読む必要があり…