Some Results on Average-Case Hardness Within the Polynomial Hierarchy

Aduri Pavan, Rahul Santhanam, N. V. Vinodchandran

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We prove several results about the average-case complexity of problems in the Polynomial Hierarchy (PH). We give a connection among average-case, worst-case, and non-uniform complexity of optimization problems. Specifically, we show that if PNP is hard in the worst-case then it is either hard on the average (in the sense of Levin) or it is non-uniformly hard (i.e. it does not have small circuits).
Recently, Gutfreund, Shaltiel and Ta-Shma (IEEE Conference on Computational Complexity, 2005) showed an interesting worst-case to average-case connection for languages in NP, under a notion of average-case hardness defined using uniform adversaries. We show that extending their connection to hardness against quasi-polynomial time would imply that NEXP doesn’t have polynomial-size circuits.
Finally we prove an unconditional average-case hardness result. We show that for each k, there is an explicit language in P TeX which is hard on average for circuits of size n k .
Original languageEnglish
Title of host publicationFSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science
Subtitle of host publication26th International Conference, Kolkata, India, December 13-15, 2006, Proceedings
PublisherSpringer Berlin Heidelberg
Pages188-199
Number of pages12
Volume4337
ISBN (Electronic)978-3-540-49995-4
ISBN (Print)978-3-540-49994-7
DOIs
Publication statusPublished - 2006

Fingerprint

Dive into the research topics of 'Some Results on Average-Case Hardness Within the Polynomial Hierarchy'. Together they form a unique fingerprint.

Cite this