A Caltech Library Service

Hardness of Approximating Σ^(p)_(2) Minimization Problems

Umans, Christopher (1999) Hardness of Approximating Σ^(p)_(2) Minimization Problems. In: 40th Annual Symposium on Foundations of Computer Science. IEEE Computer Society , Los Alamitos, CA, pp. 465-474. ISBN 0-7695-0409-4.

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

Use this Persistent URL to link to this item:


We show that a number of natural optimization problems in the second level of the Polynomial Hierarchy are Σ^(p)_(2)-hard to approximate to within n factors, for specific ε > 0. The main technical tool is the use of explicit dispersers to achieve strong, direct inapproximability results. The problems we consider include Succinct Set Cover, Minimum Equivalent DNF, and other problems relating to DNF minimization. Under a slightly stronger complexity assumption, our method gives optimal n^(1-ε) inapproximability results for some of these problems. We also prove inapproximability of a variant of an NP optimization problem, Monotone Minimum Satisfying Assignment, to within an n^ε factor using the same technique.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 1999 IEEE. Issue Date: 1999; Date of Current Version: 06 August 2002. Supported in part by NSF grant CCR-9626361 and an NSF Graduate Research Fellowship. We wish to thank Christos Papadimitriou for many useful discussions.
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number6431136
Record Number:CaltechAUTHORS:20120109-142652598
Persistent URL:
Official Citation:Umans, C.; , "Hardness of approximating Σ2p minimization problems," Foundations of Computer Science, 1999. 40th Annual Symposium on , vol., no., pp.465-474, 1999 doi: 10.1109/SFFCS.1999.814619
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:28718
Deposited On:10 Jan 2012 20:58
Last Modified:09 Nov 2021 17:00

Repository Staff Only: item control page