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 $\Sigma^p_2$-complete. We describe how strong inapproximability results for certain $\Sigma^p_2$ optimization problems can be obtained using dispersers to build error-correcting codes. Finally we adapt a learning algorithm to produce approximation algorithms for these problems.