Some Problems in Structural and Lattice Complexity

本项目主要研究计算复杂性理论，特别是结构复杂性理论以及与格问题相关的一些复杂性问题。 计算复杂性理论是研究计算问题的内在困难性的理论，无论是在最坏情况下还是在平均情况下。这一理论是基于计算问题的困难性或不可解性的所有计算机安全性的基础。研究者将研究许多复杂性类别之间的相互关系，特别是确定性P和多项式时间层次的第二层之间的关系，建立在最近关于类S2的突破之上，S2是层次结构的对称第二层类。 研究人员还探讨了一个概念的persistentNP-硬度。 这是Levin和其他人的框架中最坏情况下的困难和平均情况下的复杂性之间的一个中间水平的复杂性度量。在格问题中，研究者将寻找最短向量问题和最接近向量问题的适度有效算法，无论是在最坏情况下的措施，以及在平均情况下的措施。研究者将研究他们的连接到随机格，和潜在的应用设计安全的公钥密码系统的基础上假设的最坏情况下的复杂性。

This project is a study of computational complexity theory, in particulara study of structural complexity theory and some compelxity problemsrelating to lattice problems. Computational complexity theory isthe study of the inherent hardness of computational problems, bothin the worst-case measure as well as in the average-case measure.This theory is the underpinning of all computer security based on thehardness or insolvability of computational problems.The investigator will study the interrelationship between a number ofcomplexity classes, especially those between determinisitic P and thesecond level of the polynomial time hierarchy, building on the recentbreakthrough concerning the class S2, the symmetric second level class ofthe hierarchy. The investigator also explores a notion of persistentNP-hardness. This is to be an intermediate level of complexitymeasure between worst-case hardness and average-case complexityin the framework of Levin and others. In lattice problems, the investigator will search for moderately efficient algorithmsfor the shortest vector problem and the closest vector problem,both in the worst case measure as well as in the average case measure.The investigator will study their connections to random lattices,and potential applications to the design of secure public-keycryptosystems based on assumptions of hadness in the worst case complexity only.