This talk surveys work on classifying the complexity and approximability of problems residing in the Polynomial-Time Hierarchy, above the first level. Along the way, we highlight some prominent natural problems that are believed – but not yet known – to be
-complete. We describe how strong inapproximability results for certain
optimization problems can be obtained using
to build error-correcting codes. Finally we adapt a learning algorithm to produce approximation algorithms for these problems.