Some Problems in Structural and Lattice Complexity

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

This project is a study of computational complexity theory, in particular a study of structural complexity theory and some compelxity problems relating to lattice problems. Computational complexity theory is the study of the inherent hardness of computational problems, both in the worst-case measure as well as in the average-case measure. This theory is the underpinning of all computer security based on the hardness or insolvability of computational problems. The investigator will study the interrelationship between a number of complexity classes, especially those between determinisitic P and the second level of the polynomial time hierarchy, building on the recent breakthrough concerning the class S2, the symmetric second level class of the hierarchy. The investigator also explores a notion of persistent NP-hardness. This is to be an intermediate level of complexity measure between worst-case hardness and average-case complexity in the framework of Levin and others. In lattice problems, the investigator will search for moderately efficient algorithms for 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-key cryptosystems based on assumptions of hadness in the worst case complexity only.