CS

今後の予定

ASIACRYPT 2009の参加登録は済 問題は、日曜日中に登録を済ませるか、月曜日に登録するか、のどちらが良いか、だ。 ICS 2010... 凄く行きたいのだが、1月4日〜7日と日程がきつい。暗号の論文もあるので要注目。

グラフ理論的言い換え

CS

この時間帯に書き直しました。 グラフ理論を知っている人用の書き方をすると 直径2かつk-正則グラフの頂点数nの最大値 直径2かつk-正則平面グラフの頂点数nの最大値 を求めたいという問題です。定義から平面グラフか一般のグラフか分からなかったので両方用…

フィボナッチ数の話

CS

素数体係数多項式の拡張GCDを書かないといけないのだが, それはさておき. ストリーム版が無いけど気にするな. ;;;素朴 (define (fib1 n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib1 (- n 1)) (fib1 (- n 2)))))) ;(time (fib1 30)) ; real 0.285 ; user …

うーん

CS

ツッコミに対する反応を見て余計分からなくなった. mixi日記で、突っ込まれた点について。 量子コンピュータはチューリングマシンでできることは全てできることが証明されているので、かけ算も当然できます。量子力学的重ね合わせを使わなければ、全ての量子…

SchemeでJacobi記号

誰の役に立つのか分からないけど. 分岐が意外と多い. Jacobi記号はLegendre記号の一般化になっているので, Legendre記号もこれで求められますよ. (define (Jacobi a n) (cond ((= a 0) 0) ((= a -1) (cond ((= (modulo n 4) 1) 1) ((= (modulo n 4) 3) -1)))…

undecidable problems

CS

とりあえず10個かー. 授業で証明読んだもの 停止問題とそのヴァリアント ビジービーバー ライスの定理 L(PDA)?={0,1}^*, L(PDA1)?=L(PDA2) PCP (Postの方) 証明知らないもの ヒルベルトの第10問題 ワンのタイル 読みたいもの DBLPから見繕う. 群同型 en.wiki…

Wolfram|Alpha

CS

簡易Mathematicaとしては便利なんじゃないでしょうか. 例: (a+b)^2 x^2+2x=y^2+3 factor 2x^5 - 19x^4 + 58x^3 - 67x^2 + 56x - 48 factor x^110+1 in GF(5) 素数位数の体なら因数分解できる factor x^10-1 in Z/44Zとかは因数分解してくれない

アルゴリズムの名前

CS

今回の内容は以前当ブログに書いた「diff with C++」の記事をもっと濃くした感じになっていて、編集距離やLCS、SESの解説に始まり、Subversionのdiffエンジンや拙作のdtlで使われているO(NP)という差分アルゴリズムについて解説しています。 O(NP)や、それに…

宣伝

CS

4/24発売だそうです。 確率と計算 ―乱択アルゴリズムと確率的解析―作者: Michael Mitzenmacher,Eli Upfal,小柴健史,河内亮周出版社/メーカー: 共立出版発売日: 2009/04/24メディア: 単行本購入: 2人 クリック: 32回この商品を含むブログ (11件) を見る 目次…

Goldreichのブログ?

CS

my choices [Oded Goldreich] RSSが配信されているのでそっちで読んだ方が見易いかもしれません. 理想としてはWordpressに移行してTeXプラグインを入れて書いてほしい. TrevisanやTaoみたいに.

STOC 2009

STOC 2009 - Accepted Papers (with Abstracts) 格子暗号は2件. Peikertだけかと思ったら, Gentryが凄いの出してきた. イデアル格子ベースの暗号でNC1の回路をシミュレートできるらしい. エラーが足されるせいで, O(log n)までなのかな. エラーを外せれば任…

Reed-Muller符号のリスト復号

P. Gopalan, A.R. Klivans, and D. Zuckerman. “List-Decoding Reed-Muller Codes over Small Fields.” (STOC 2008) 中身読んでないのでメモだけ.r次のRM符号RM(r,m,2)のメッセージ空間は, m変数r次のF_2上多項式の集合. 符号が入っている空間はF_2^mの各要…

証明の手直し

CS

間違っているところがあったので直そうと思ったら,不完全ベータ関数についてのメモが見つからない. どこ行ってん. Abramowitz and Stegun, Page 263に載ってた. これ引けばいいのかねぇ.

CS

適当な時間に東野圭吾のアレを読むことをメモ. 例の問題が出てくるのは本当だろうか.

F_3上の多項式

(k:0以上の整数) はF_3上でに因数分解でき, それぞれ既約な気がする. d次の多項式fのF_3上の既約性を判断するには, F_3のd次拡大を考えてやる. すると多項式がd次以下のdの約数の次数を持つモニックかつ既約な多項式の積になっている. なので最初に rem f = …

ランダム生成について (今更)

CS

d.y.d. - 23:51 06/10/19 - ランダム生成 あー, 2年経ってようやく, MCMCの話題だということに気づいた(;´Д`) 重ならない円を1000万個という例2は, モンテカルロ法のチュートリアルに載っている. [cond-mat/9612186] Werner Krauth - “Introduction To Mont…

CS

[0810.1018] Cristopher Moore, Alexander Russell “A simple constant-probability RP reduction from NP to Parity P” 解析的数論というかWeilの有限体上の指標和に関する上限式の結果を使うと戸田の定理の証明の一部が楽になるとかなんとか. (あんまり詳…

CS

[0810.0033] M. H. Freedman “Complexity Classes as Mathematical Axioms” (ephermata: What does knot theory have to do with P^#P != NP ?) P^{PP}≠NPを仮定するとジョーンズ多項式経由で結び目の方で面白い結果が得られるとか.

5-smooth数を下からn個

CS

2^i * 3^j * 5^k なる整数 どう書く?org どう書く?org 7667 leque: 出題時に考えていた答。平衡木を使うので、...(2^i * 3^j * 5^k なる整数) - 投稿の詳細 nobusun 求める数の個数 n なのに 時間計算量 O(log n) というのがよく判らないんです。 素人考え…

ISAAC 2008のaccepted papers

The 19th International Symposium on Algorithms and Computation (ISAAC 2008) (via:dense outliers: ISAAC 2008 accepted papers) ぼけーっと見てたら, Giovanni Di Crescenzo. 3-Round NP Arguments in the BPK Model with Optimal Soundness and Zero-K…

CS

>くるるさんがTuring機械と見做せない「機械」としてどのようなものを想定されているのか想像が付きません。 いくらでもあると思うんですが。AIBOとかブルドーザーとか水車とか。アナログな入出力があった時点でTuring機械とはみなせないわけで。もう少し文…

ゲームと困難性

前置き CiNii - ぷよぷよはNP完全 はてなブックマーク - CiNii - ぷよぷよはNP完全 全て頭に一般化が付きます. 色々結果はありますが, 問題の定式化によって当然難しさが変わりますのでご注意を. 定義は元論文を見て確認してください. 2人ゲーム オセロ PSPA…

ビザンチン合意と一斉射撃問題

某所で聞き損ねたこと. そういえばCAの方の文脈で一斉射撃問題というのがあるそうだ. 一斉射撃問題 横一列に兵士が並んでいて, 適当な位置に一人将軍が居る. 命令の伝達は隣の人にしか行えない. このとき, 一斉に射撃するにはどうするか. 兵士間の伝達経路を…

Rの練習

2次元ランダムウォーク どう書く?org 1次元版が1行で書けてびっくりですよ. wにf.xをapplyしようとしてこけたのでリストに変換後lapplyしてunlistしてベクトル化. もっといいデータ構造を使うと3次元表示のときに点と点の間に線を引けるのではないかと予想.…

コーシー分布

平均が存在しないことで有名な分布. それはさておき, Cy(m,s)をコーシー分布とする. 確率密度関数はである. 0<e<1かつs>1についてCy(m,s)とCy(m,s+e)と2つ考えたときに統計的距離は2eで抑えられる.真面目に積分した. arctanとか久しぶりに見たよ(;´Д`) 以下証明. Δを</e<1かつs>…

暗号学的な (符号理論での) 通信路のモデル化

色々端折った説明.通信路上でエラーが載るので, そのエラーを訂正するために使われるのが誤り訂正符号である. さて, 符号理論ではエラーのモデルとして以下の二つが考えられる. シャノン 1文字ごとにエラーが付くか付かないかが決まる (また各エラーは独立で…

サンプリング

Knuth本の2巻の擬似乱数生成のところにあったなと思って3版の日本語版をゼミ前に確認. 正規分布のサンプリングとかだとそこそこ書いてあるが, 難しい分布になると途端に歯切れが悪くなっている. 更に, 古い論文しか引いてないので, 2版から更新されていない…

可逆計算のメモ

CS

ref:どこが面白いの?可逆計算 -- コンピューティングと北極グマ - 檜山正幸のキマイラ飼育記 上記記事を読んで適当な話をメモしておく.そういえば量子だと観測しない限り可逆だなぁと思いました (又聞き). あと素子自体をビリヤードみたいにするタイプの可…

2chのスレッドで反応するのは良くないなぁと思ったので, ここにメモを残しておきます. まぁそもそも仮定につっこむのもアレですが. 格子の被覆半径を計算する問題がNPに属することをわしが証明したら、 V. Guruswami, D. Micciancio, and O. Regev "The comp…

メモ

CS

誤差付き計算を扱うことになった. 色々と調べたいのだが, どうしたもんだか. xの誤差が±2^{-k}であるとき, exp(-x)の誤差はどれだけ広がるのか? また誤差を±2^{-k/2}に収めるアルゴリズムがあるとしてその計算時間はいかほどか? 精度保証付き数値計算で調べ…

FOCS 2008 - Accepted Papers

CS

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で考え…

京都賞

CS

今年は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…

ポンピング補題の練習

CS

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

メモ

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

○×ゲーム

CS

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

下の話について

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

<a href="http://projecteuler.net/index.php?section=problems&id=188">Problem 188</a>

タワー表記かよ. 実はあっさり解ける問題. (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で解が一意に定まるもの. 手を動かすとアレの解の構造を決定する問題になるの…

<a href="http://citeseerx.ist.psu.edu/">CiteSeerX alpha</a>

CS

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

メモ

CS

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 数え上げ. 漸化式を立ててメモ化で終了.

安定結婚問題

CS

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

理系のための口頭発表術

CS

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