The classical theory of NP-completeness shows that many optimization problems of practical interest are hard to solve: i.e., NP-hard problems that have no polynomial-time algorithms (assuming P is not equal to NP). A popular method for dealing with such an NP-complete problem is to try to compute approximate solutions: i.e., solutions whose cost is within some multiplicative factor of the cost of the exact solution. The focus of this project is to demonstrate that computing approximate solutions for NP-hard problems is no easier than computing exact solutions. The underlying idea which is exploited, is that of a new probabilistic definition of the NP complexity class, a definition based on probabilistically checkable proofs (PCP's). Some of the major goals of the project include: (1) To better understand the approximability of NP-hard optimization problems (including cataloging the hardness of approximation of many problems, improving existing results about the hardness of approximation, and understanding the limitation of these techniques); (2) To develop further connections between the theory of PCP's and cryptography; (3) To improve existing ways of representing data by error-correcting codes; (4) To simplify the techniques used in the proof of this new definition of NP. The Educational Component of this CAREER Grant includes: (a) Development of CORE undergraduate computer science courses (including Theory of Computation and Applied Discrete Mathematics); (b) Development of a graduate computer science course and a corresponding text dealing with PCP's and (approximate) complexity theory.
