CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20200127-140148446

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

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200127-140148446

Abstract

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
https://doi.org/10.1007/11750321_33DOIArticle
https://rdcu.be/b3YncPublisherFree ReadCube access
Additional Information:© 2006 Springer-Verlag Berlin Heidelberg. Supported by NSF grant CCF-0346991 and an Alfred P. Sloan Research Fellowship.
Funders:
Funding AgencyGrant Number
NSFCCF-0346991
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:https://resolver.caltech.edu/CaltechAUTHORS:20200127-140148446
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100950
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:28 Jan 2020 19:04
Last Modified:05 May 2020 22:26

Repository Staff Only: item control page