■

Noga Alon "Graph Powers"

師匠から貰った論文の中にあった一本。タイトルが秀逸。
Powersは累乗のことです。G:グラフとしたら、って感じ。powersの方は頂点数が累乗で増えていくので、中々大変なことに。

小柴健史「現代暗号への量子アルゴリズムによる攻撃」

「数理科学No.492 June 2004 特集/量子アルゴリズムの新地平」から。
Brassardが言っていたのはそういうことか。確かに暗号文空間は工学的な要請からcoNPじゃないときつい。すると大方の予想では暗号文解読はNP-hardでは無い(NP≠coNPと予想する人が多いので)。ということで暗号のアルゴリズムは程々の難しさが要請される。けど、程々だと量子アルゴリズムが怖い。
あ、4番の隠れ線形構造の話は面白かったのでまた調べよう。BonehとLiptonがShor*1のアルゴリズムを拡張したらしいよ。
素因数分解/離散対数は隠れ部分群問題の特殊な場合と定式化できるらしい。で、有限Abel群だとあっさりと解けるらしい。
SVPと正二面体群の隠れ部分群問題との関連も気になるな。Aharonov,Regevのの論文も探そう。この前、間違えて読んだ論文のことだ、これ。

*1:どっかでショールって訳している人が居たな