Some Results on Average-Case Hardness Within the Polynomial Hierarchy

DOI10.1007/11944836_19MaRDI QIDQ5385985zbMATH OpenOpenAlexFDO

Authors Aduri Pavan, Rahul Santhanam, N. V. Vinodchandran

Publication date 17 April 2008

Published in FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://www.pure.ed.ac.uk/ws/files/17974469/Pavan_Santhanam_ET_AL_2006_Some_Results_on_Average_Case_Hardness_within_the_Polynomial_Hierarchy.pdf

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
• scientific article; zbMATH DE number 5081744
• Fundamentals of Computation Theory
• Worst-Case to Average-Case Reductions Revisited
• Average-case intractability vs. worst-case intractability

Cited in

(8)

• PAC-learning gains of Turing machines over circuits and neural networks
• Circuit lower bounds for average-case MA
• Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• The 1-Versus-2 Queries Problem Revisited
• scientific article; zbMATH DE number 7758317 (Why is no real title available?)
• Sets computable in polynomial time on average
• The 1-versus-2 queries problem revisited

This page was built for publication: Some Results on Average-Case Hardness Within the Polynomial Hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5385985)