STOC 2007

研究

最近 accepted paper list ばっかり載せていますが，今回はSTOC 2007です．

量子計算関係（だと思われるもの）は以下の４本でした．

  1. F. Magniez, A. Nayak, J. Roland and M. Santha, "Search via Quantum Walk."
  2. D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz and R. de Wolf, "Exponential separations for one-way quantum communication complexity, with applications to cryptography."
  3. G. Gutoski and J. Watrous, "Toward a general theory of quantum games."
  4. P. Hoyer, T. Lee and R. Spalek, "Negative weights make adversaries stronger."

学生時代，Grover search系の研究をしていたので，特に１番目の論文に興味を惹かれます．この論文はAmbainisのelement distinctness アルゴリズムの流れを引いており，quantum walkを一般的に探索アルゴリズムとして用いる手法を提案しているようです．

量子計算以外で個人的に興味があるのは

  1. I. Haitner and O. Reingold, "Statistically-Hiding Commitment from Any One-Way Function."
  2. M. Fürer, "Faster Integer Multiplication."

１番目の結果の一方向性関数から統計的秘匿性を持つビットコミットメントの構成は暗号理論における長年の未解決問題だったわけで，非常に重要な結果だと言えるかと思います．

２番目の論文ですが，掛け算を高速化できるってすごいですね．論文をオンラインで探してみたんですが，見つかりませんでした．残念．

そういえば，こないだのエントリに書いたSanthanamの論文もやはり通ってますね．

あ，あとこないだフィールズ賞とった Terence Tao の論文も出てますね．

  • v. vu and T. Tao, "The condition number of a randomly perturbed matrix."

ミーハーですみません．