FOCS 2006の<a href="">accepted papers</a>出ましたよ.

Computational Complexity - FOCS Accepts and a Movieから.

学習関係のは, Regev暗号やらAjtai-Dwork暗号やらを使って学習の不可能性を議論しているんだったかと (学習のことはよぉ知らんので受け売りで.) なのでこれは格子関係. Razborov and Yekhaninのは, 群を決めてrestricted modelで下限を示しているらしい. D. Boneh, E.-J. Goh, and K. Nissim. Evaluating 2-DNF Formulas on Ciphertexts (TCC 2005)ってO(n^{1/3})の計算量でPIRやってた気がするな. これがOptimalなの? あ, ECCC TR06-050を読んだらD. Boneh, E.-J. Goh, and K. Nissim. Evaluating 2-DNF Formulas on Ciphertexts (TCC 2005)を引いてない. 俺が間違ってんのかな.

  • A. A. Razborov and S. Yekhanin. An \Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval. (ECCC TR06-050)
  • Boaz Barak, Manoj Prabhakaran and Amit Sahai. Concurrent Non-Malleable Zero Knowledge.
  • Venkatesan Guruswami and Anindya Patthak. Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets.
  • Adam R. Klivans and Alexander A. Sherstov. Cryptographic Hardness Results for Learning Intersections of Halfspaces. (ECCC TR06-057)
  • Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai. Cryptography from Anonymity. (Cryptology ePrint Archive - 2006/084)
  • Venkatesan Guruswami and Prasad Raghavendra. Hardness of Learning Halfspaces with Noise. (ECCC TR06-061)
  • Silvio Micali, Rafael Pass and Alon Rosen. Input-Indistinguishable Computation.
  • Russell Impagliazzo, Ragesh Jaiswal and Valentine Kabanets. List-decoding direct product codes and uniform hardness amplification.
  • Vitaly Feldman and Parikshit Gopalan and Subhash Khot and Ashok Kumar Ponnuswami. New Results for Learning Noisy Parities and Halfspaces. (ECCC TR06-059)
  • Danny Harnik and Moni Naor. On the Compressibility of NP Instances and Cryptographic Applications. (ECCC TR06-022 R01)
  • Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan. Statistical Zero-Knowledge Arguments for NP from Any One-Way Function. (ECCC TR06-075)
  • Eli Ben-Sasson, Swastik Kopparty and Jaikumar Radhakrishnan. Subspace Polynomials and List Decoding of Reed-Solomon Codes.