STOC 2007のaccepted papers出たよ
Papers accepted for presentation in STOC 2007
分かるものにはリンクを張っておく.
暗号
- Iftach Haitner and Omer Reingold.
- Statistically-Hiding Commitment from Any One-Way Function (Cryptology ePrint Archive 2006/436)
- 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.
- On Achieving the ''Best of Both Worlds'' in Secure Multiparty Computation (Cryptology ePrint Archive 2006/455)
- 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.
- Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors (Oded Regev (pdf))
- Khotの結果の改良
- Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors (Oded Regev (pdf))
- 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通ったのかよ（；´Д｀)
- Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors (ECCC TR06-147)
他
- Martin Fürer.
- Faster Integer Multiplication (TR CSE-07-001, PSU)
- O(n log{n} loglog {n})より高速だとか. 下界の予想はΩ(n log{n}).
- Faster Integer Multiplication (TR CSE-07-001, PSU)
- Andreas Björklund, Thore Husfeldt, Petteri Kaski and Mikko Koivisto.
- Fourier Meets Möbius: Fast Subset Convolution
- 最小シュタイナー木問題を高速に解けるらしい. あと動的計画法より良いアルゴリズムとか書いてあるが.
- Fourier Meets Möbius: Fast Subset Convolution
が気になった.
