近年来，编码理论与计算复杂性理论产生越来越紧密的联系：一方面，人们需要判断许多编码问题的复杂性来指导具体算法设计；另一方面，一些特定的编码方式成为复杂性理论中的工具，促进复杂性理论的发展。编码理论与计算复杂性之间的交叉成果又促进了密码学的发展。本项目将研究如下问题：1）分析一些编码问题的复杂性，发现新的NP-难问题；2）改进特定编码方式的编解码算法，比如Reed-Solomon码和Reed-Muller码的列译码算法等；3）研究Learning with errors(LWE)问题的复杂性；4）分析与攻击基于两个难问题Learning parity with noise(LPN)和LWE的密码系统，找到一些有效的分析与攻击方法。希望本项目的研究促进密码学、编码理论与计算复杂性的交叉理论发展。

Recently, more and more relationships between coding theory and computation complexity are discovered. On the one hand, we would know the complexity of some coding problems to direct the algorithm designs. On the other hand, some codes are applied to the theory of computation and make it forward. Furthermore, the compounded results in coding theory and computation complexity result in the development of cryptography. We will investigate the following problems: (1) Analyze the complexity of some coding problems, and look for new NP-hard problems; (2) Improve the encoding and decoding algorithms for certain well-known codes, e.g. the list-decoding algorithms for Reed-Solomon and Reed-Muller Codes; (3) Investigaet the complexity of Learning with errors(LWE); (4) Analyze and Attack cryptosystems based on the hardness of the two problems Learning Parity with Noise (LPN) and Learning With Errors (LWE), and find some efficient methods. We hope that our research will push forward the mixed research among cryptography, coding theory and computation complexity.