■

crypt
  • なんでROMでの証明を俺が書いてんだって話ですよ, 本当に. RO嫌いな方なのに理解が進む進む.
  • Benny Applebaum, David Cash, Chris Peikert, Amit Sahai “Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems” (CRYPTO 2009)
    • AppelbaumがLPN仮定からKDM-CPA secureなSKE, 線形分伸ばす準線形時間擬似乱数生成器, weak PVRF (だっけか?) を作ったので, 3人位加わって拡張したらしい. (AppelebaumのサイトにいったらTech. Rep.扱いの論文があった.)
    • LWE仮定からKDM-CPA secureなPKEが出来る. ただし関数は秘密鍵のアフィン変換みたいなもの. s∈Z_p^nを秘密鍵として, <s,t>+w mod pという種類の関数のみを扱っている.
    • 証明は暗号と線形代数と多次元ガウス分布が分かっていればすぐ読めてしまう. 基本的にはRegev暗号なんだけど元のZ_qと鍵の作り方が変わっていてそこがミソになっている.

BDD, uSVP, GapSVP.

crypt

Lyubashevskyが, Peikertのテクニックを用いることで, 近似度をO(√n)分悪くすることでuSVPはGapSVPに帰着できることを示していましたが (ePrintにある), BDDについても出来るということをMicciancioとの共著で書いてます. CRYPTO '09に通ったそうなので, 皆さんLyubashevskyのサイトからダウンロードして読むように.

アルゴリズムの名前

CS

今回の内容は以前当ブログに書いた「diff with C++」の記事をもっと濃くした感じになっていて、編集距離やLCS、SESの解説に始まり、Subversionのdiffエンジンや拙作のdtlで使われているO(NP)という差分アルゴリズムについて解説しています。
O(NP)や、それによく似たO(ND)をはじめとするエディットグラフを使って差分を求めるアルゴリズムは普段何気なく使っているdiffコマンドや各種バージョン管理システムで使われていることからもわかるようにとても有用であり、アルゴリズム自体の美しさやスマートさにも目を見張るものがあります。興味がある方はぜひ手にとって読んでみてください。本記事を通してdiffのアルゴリズムのおもしろさが伝われば幸いです。

「O(NP)」や「O(ND)」というのは各々のアルゴリズムの計算量のことであって名前にするのはどうなんでしょう。
Wu, Manber, Myers, Millerのアブストにあるthe O(ND) algorithm of MyersとかってのはMyersのO(ND) (計算量) アルゴリズムって意味であって、アルゴリズムの名前じゃありません。また、最近の編集距離関係の論文を見てもO(NP)でアルゴリズムを指している例は見当たりませんでした。

ということで「O(NP)差分アルゴリズム」ならセーフだけど「O(NP)という差分アルゴリズム」だとアウトじゃぁないでしょうか。

修正されたようです. よかったよかった( ´ー｀)

■

日常
  • 終わらせてないのがある.
    • 1つはフーリエ変換がえぐいことになるので見たくない. 解析的数論とか知るかー.
    • しかも既存方式より効率が良くないっていう. なんか別のと組み合わせるべきか. ただ別のも帰着がうまくいかないのでどうしようもない. ぬぅ.
  • 決定性にすると抜けられてしまうのが良くないんだよねー.
    • むしろ不可能性を証明する方向はどうだろう.

>

単純な場合の格子点の個数

math

格子点の個数がわからない
僕は組合せの話は知らない／分からないのですが、なぜか次のタイプの問題にしばしば遭遇します； R^nの第1象限 {(x_1, ..., x_n)∈R^n | x_1≧0, ..., x_n≧0 } の範囲で、非負整数kに対して、

  • 方程式 x_1 + ... + x_n = k
  • 不等式 x_1 + ... + x_n ≦ k

を考えます。この方程式／不等式の整数解（格子点）は何個あるんでしょう？ アルゴリズムとか近似とか評価とか漸化式とか母関数とかじゃなくて、nとkによるズバリあからさまな初等的表示が欲しいんですけど。そんなのないのかな？ どなたかご存知でしょうか。

上は, k個のボールとn-1個の仕切りの並べ方になるので, (n-1+k)!/k!(n-1)! = \left(\begin{array}n+k-1&\\k\end{array}\right).
下は, スラック変数x_{n+1}を突っ込んで, {x \in Z^{n+1} | x_1+...+x_n+x_{n+1}=k, x_{i}≧0 for all i}と方程式の解の個数に帰着出来て, \left(\begin{array}n+k&\\k\end{array}\right).

ということでコメント欄に[1..100]>=penさんが書いてる通りです.

ところで下の方って大学入試に出ましたっけねぇ?

簡単な拡張として,
\{(x_1, ..., x_n) \in \mathbb{R}^n | x_1 \geq 0, ..., x_n \geq 0, x_1 a_1 + \cdots + x_n a_n \leq k \} \cap \mathbb{Z}^n \}
の個数を数える問題が考えられます. a_i=1が元の問題です. n=2で母関数やら複素解析が出始めて, n=3だといやな関数になります.
より拡張すると, n次元空間の領域中の格子点を数え上げる問題になり,

Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra (Undergraduate Texts in Mathematics)

Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra (Undergraduate Texts in Mathematics)


と1冊の本になるんですって.
1章で, 上の簡単な拡張を扱っているそうで.