STOC 2007のaccepted papers出たよ

Papers accepted for presentation in STOC 2007


  • Iftach Haitner and Omer Reingold.
  • Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz and Ronald de Wolf.
    • Exponential separations for one-way quantum communication complexity, with applications to cryptography
  • Jonathan Katz.
  • Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai.
    • Zero-Knowledge from Secure Multiparty Computation
  • Rafael Pass and Muthuramakrishnan Venkitasubramaniam.
    • An Efficient Parallel Repetition Theorem for Arthur-Merlin Games
  • Kobbi Nissim, Sofya Raskhodnikova and Adam Smith.
    • Smooth Sensitivity and Sampling in Private Data Analysis


  • Ishay Haviv and Oded Regev.
  • Chris Peikert and Alon Rosen.
    • Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors (ECCC TR06-147)
      • 特殊な格子の集合を考えると, そのうえではlog nの損失でa/w-connectionが言える. (ただし具体的な構造は決めていない気がする.)
      • STOC通ったのかよ(;´Д`)

  • Martin Fürer.
    • Faster Integer Multiplication (TR CSE-07-001, PSU)
      • O(n log{n} loglog {n})より高速だとか. 下界の予想はΩ(n log{n}).
  • Andreas Björklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto.
    • Fourier Meets Möbius: Fast Subset Convolution
      • 最小シュタイナー木問題を高速に解けるらしい. あと動的計画法より良いアルゴリズムとか書いてあるが.