A Caltech Library Service

Optimization Problems in the Polynomial-Time Hierarchy

Umans, Christopher (2006) Optimization Problems in the Polynomial-Time Hierarchy. In: Theory and Applications of Models of Computation. Lecture Notes in Computer Science. No.3959. Springer , Berlin, pp. 345-355. ISBN 978-3-540-34021-8.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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 Σ^p₂-complete. We describe how strong inapproximability results for certain Σ^p₂ 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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ReadCube access
Additional Information:© 2006 Springer-Verlag Berlin Heidelberg. Supported by NSF grant CCF-0346991 and an Alfred P. Sloan Research Fellowship.
Funding AgencyGrant Number
Alfred P. Sloan FoundationUNSPECIFIED
Subject Keywords:Approximation Algorithm; Boolean Circuit; SIGACT News; Constant Depth Circuit; Circuit Lower Bound
Series Name:Lecture Notes in Computer Science
Issue or Number:3959
Record Number:CaltechAUTHORS:20200127-140148446
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100950
Deposited By: Tony Diaz
Deposited On:28 Jan 2020 19:04
Last Modified:05 May 2020 22:26

Repository Staff Only: item control page